将所有的信息插到Trie树里，对每一条密码，都去已经建好的Trie树中找一次。
若这条密码的长度比所有 是它的前缀的信息 的长度大，那么每次遇到完整的信息就统计一次答案；
反之则需统计这条密码是多少条信息的前缀，用一个cnt[i]来记录在Trie树中经过i这个点的信息有多少。
比较坑的地方是 会有相同的信息，所以还另需记录每条信息的数量。
#include<complex> #include<cstdio> using namespace std; const int N=5e5+7; int n,m,Tnum,ans; int trie[N][2],sum[N],num[N],cnt[N]; char s[N]; bool flag[N]; int qread() { int x=0; char ch=getchar(); while(ch<'0' || ch>'9')ch=getchar(); while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } void Insert(int a) { int root=0; for(int i=1;i<=a;i++) { if(!trie[root][num[i]]) trie[root][num[i]]=++Tnum; root=trie[root][num[i]]; cnt[root]++; } flag[root]=1;sum[root]++; } int Query(int a) { int root=0,res=0; for(int i=1;i<=a;i++) { if(!trie[root][num[i]])return res; root=trie[root][num[i]]; if(flag[root])res+=sum[root]; } res+=cnt[root]; if(flag[root])res-=sum[root]; //若到root是一条完整的信息,则需减去这条信息的数量(该条信息被统计了两次) return res; } int main() { scanf("%d%d",&n,&m); int a; for(int i=1;i<=n;i++) { a=qread(); for(int j=1;j<=a;j++) num[j]=qread(); Insert(a); } for(int i=1;i<=m;i++) { a=qread(); for(int j=1;j<=a;j++) num[j]=qread(); printf("%d ",Query(a)); } return 0; }