正确率极高,但是7pts
查看原帖
正确率极高,但是7pts
241817
Chancylaser楼主2023/7/11 11:30

下载了数据,正确率挺高,但是有的答案比标准答案稍大。

// Date:       2023/7/11
// Programmer: Chancylaser
// 颓啥颓,做题去 | 不再做小丑 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e6+5;

int n,m;
int trie[N][2],tot;
int sum[N],ed[N];
void Insert(string s){
	int len=s.size(), p=0;
	sum[0]++;
	for(int i=1;i<len;i++){
		int t=s[i]-'0';
		if(!trie[p][t]) trie[p][t]=++tot;
		p=trie[p][t];
		sum[p]++;
	}
	ed[p]++;
}

int query(string s){
	int len=s.size(), p=0;
	int ans=0;
	for(int i=1;i<len;i++){
		int t=s[i]-'0';
		if(!trie[p][t]) return ans+sum[p];
		ans+=ed[p];
		p=trie[p][t];
	}
	return ans+sum[p];
}

string a;

int main(){
//	freopen("1.in","r",stdin);
//	freopen("qwq.out","w",stdout);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int len,x; a="";
		
		cin>>len;
		a+='q';
		for(int j=1;j<=len;j++){
			cin>>x;
			if(x==0) a+='0';
			else a+='1';
		}
		Insert(a);
	}
	
	for(int i=1;i<=m;i++){
		int len,x; a="";
		
		cin>>len;
		a+='q';
		for(int j=1;j<=len;j++){
			cin>>x;
			if(x==0) a+='0';
			else a+='1';
		}
		
		cout<<query(a)<<"\n";
	}
	return 0;
}

2023/7/11 11:30
加载中...