1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int N=5110000; int id,ch[N][2],a[N],ed[N],ed2[N]; void ins() { int p=0; for(int i=1;i<=a[0];i++) { int j=a[i]; if(!ch[p][j])ch[p][j]=++id; p=ch[p][j]; ed2[p]++;//ed2表示前缀的存在 } ed[p]++;//ed表示完成的一条信息的存在 } int query() { int p=0,ret=0; for(int i=1;i<=a[0];i++) { int j=a[i]; if(!ch[p][j])return ret; p=ch[p][j]; ret+=ed[p]; } return ret+ed2[ch[p][0]]+ed2[ch[p][1]]; //为什么不是return ret+ed2[p]? 因为每天信息都是自己的前缀,要避免重复计算 } int main() { int n,m;scanf("%d%d", &n, &m); id=0;memset(ch,0,sizeof(ch));memset(ed,0,sizeof(ed)); memset(ed2,0,sizeof(ed2)); for(int i=1;i<=n;i++) { scanf("%d", &a[0]);for(int j=1;j<=a[0];j++) scanf("%d", &a[j]); ins(); } for(int i=1;i<=m;i++) { scanf("%d", &a[0]);for(int j=1;j<=a[0];j++) scanf("%d", &a[j]); printf("%d\n", query()); } return 0; }
- 1
信息
- ID
- 3245
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 50
- 已通过
- 16
- 上传者