1 条题解

  • 0
    @ 2025-10-8 17:04:21
    #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

    *【字典树】秘密信息[USACO08DEC] Secret Message G

    信息

    ID
    3245
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    50
    已通过
    16
    上传者