0分球调
查看原帖
0分球调
573334
yzkadbq_qwq楼主2023/5/16 19:19
#include<bits/stdc++.h>
using namespace std;
struct trie{
	int cnt,son[2],all;
} ch[500001];
int top=0,n,m;
void ins(bool a[],int len){
	int p=0;
	for(int i=1;i<=len;i++){
		if(!ch[p].son[a[i]]) ch[p].son[a[i]]=++top;
		p=ch[p].son[a[i]];
		ch[p].all++;
	}
	ch[p].cnt++;
	return;
}
int query(bool a[],int len){
	int p=0,ans=0;
	bool flag=0;
	for(int i=1;i<=len;i++){
		if(ch[p].son[a[i]]) p=ch[p].son[a[i]];
		else{
			flag=true;
			break;
		}
		if(ch[p].cnt) ans+=ch[p].cnt;
	}
	if(!flag){
		ans+=ch[p].all;
		if(ch[p].cnt){
			ans-=ch[p].cnt;
		}
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int len;
		cin>>len;
		bool a[len+1];
		for(int j=1;j<=len;j++){
			int tmp;
			cin>>tmp;
			if(tmp){
				a[i]=1;
			}else{
				a[i]=0;
			}
		}
		ins(a,len);
	}
	for(int i=1;i<=m;i++){
		int len;
		cin>>len;
		bool a[len+1];
		for(int j=1;j<=len;j++){
			int tmp;
			cin>>tmp;
			if(tmp){
				a[i]=1;
			}else{
				a[i]=0;
			}
		}
		cout<<query(a,len)<<"\n";
	}
	return 0;
}
2023/5/16 19:19
加载中...