萌新刚学OI,求助字典树
查看原帖
萌新刚学OI,求助字典树
316322
hzoi_liuchang楼主2020/7/23 18:53
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e7+5;
char c[maxn];
int tr[maxn][3],cnt[maxn][3],tot,ed[maxn][3];
void ad(char s[]){
    int len=strlen(s);
    int now=0;
    for(int i=0;i<len;i++){
        int t=s[i]-'0';
        if(tr[now][t]){
            cnt[now][t]++;
        } else {
            tr[now][t]=++tot;
            cnt[now][t]=1;
        }
        if(i==len-1) ed[now][t]++;
        now=tr[now][t];
    }
}
int cx(char s[]){
    int len=strlen(s);
    int now=0,ans=0,js=0,jud=0,t;
    for(int i=0;i<len;i++){
        t=s[i]-'0';
        if(tr[now][t]){
            js+=ed[now][t];
            if(i!=len-1)now=tr[now][t];
        } else {
            jud=1;
        }
    }
    if(jud) return js;
    else return js-ed[now][t]+cnt[now][t];
}
char s[maxn];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        int aa;
        for(int j=1;j<=t;j++){
            scanf("%d",&aa);
            s[j-1]=aa+'0';
        }
        s[t]='\0';
        ad(s);
    }
    for(int i=1;i<=m;i++){
        int t;
        scanf("%d",&t);
        int aa;
        for(int j=1;j<=t;j++){
            scanf("%d",&aa);
            s[j-1]=aa+'0';
        }
        s[t]='\0';
        printf("%d\n",cx(s));
    }
    //printf("%d\n",cnt[0][0]);
    return 0;
}
2020/7/23 18:53
加载中...