题解 P2922 【[USACO08DEC]秘密消息Secret Message】

· · 题解

典型的字典树统计题。

首先是读入。这道题全部采用2进制，也就是说只有0和1两个字符/数字，那么我们直接把它们当成字符用好了。

然后建树，也是一般的字典树建树法，只是把字母换成了0和1而已，这里不多讲。

一边建树，一边在这串数列中走过的路径中的sum+1，sum代表有sum个单词（？）经过这个节点。

当一个单词（？）插完以后，在当前节点（即该单词的最后一个数字）的end上+1，end代表有end个单词（？）在这个节点终结。

注意可能会有重复的信息，也就是说可能会有多条信息在同一个节点终结，所以这里的end是数字而不是布尔型。

然后读入待查询的信息，就像普通字典树查询一样地往下走，一边走一边把沿途的end值加起来。

循环结束，有两种情况：一是该信息全部走完，二是再往下走没有与该信息相符的节点了。

第一种情况，当前的答案要减去当前节点的end值再加上当前节点的sum值（想一想，为什么）。

第二种情况，直接输出答案。

显然比待查询的信息长的信息，如果与待查询信息有相同前缀的话，一定会经过待查询信息终结的节点。

如果待查询信息无法终结，说明没有比该信息长且前缀是该信息的信息，所以不能加上sum。

如果信息终结，那么当前节点的sum值所包含的信息一定与其有相同前缀，但sum所包含的信息有可能刚好在该节点终结，

所以要减去end值。

···C++

#include<bits/stdc++.h>
using namespace std;
struct cow{
    int nex[2],sum,end;
}t[500001];
int a[10001];
inline int read()
{
    int data=0,w=1; char ch=0;
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
    return data*w;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m,js=1;
    memset(t,0,sizeof(t));
    m=read();n=read();
    for (int i=1;i<=m;i++)
    {
        int len;
        len=read();
        for (int j=1;j<=len;j++) a[j]=read();
        int now=1;
        for (int j=1;j<=len;j++) 
        {
            if (t[now].nex[a[j]]!=0) now=t[now].nex[a[j]];
            else
            {
                js++;
                t[now].nex[a[j]]=js;
                t[js].nex[1]=t[js].nex[0]=0;
                now=js;
            }
            t[now].sum++;
        }
        t[now].end++;
    }
    for (int i=1;i<=n;i++)
    {
        int len;
        len=read();
        for (int j=1;j<=len;j++) a[j]=read();
        int now=1,ans=0;
        bool flag=true;
        for (int j=1;j<=len;j++)
        {
            if (t[now].nex[a[j]]!=0) now=t[now].nex[a[j]];
            else 
            {
                flag=false;
                break;
            }
            ans+=t[now].end;
        }
        if (!flag) cout<<ans<<endl;
        else cout<<ans+t[now].sum-t[now].end<<endl;
    } 
    return 0;
} 
···