下载了数据,正确率挺高,但是有的答案比标准答案稍大。
// 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;
}