Secret Message G

· · 个人记录

题目大意

给定 m 条信息和 n 条密码。求对于每条密码，有多少条信息与该密码满足一个是另一个的前缀。

题目分析

看到询问前缀，很容易想到对信息建立字典树。

规定字典树的左孩子代表 0，右孩子代表 1。同时在每个节点加一个计数器 end 表示有多少条信息在这里结尾。

关于查询，需要进行分类讨论：

  1. 密码长度 > 信息长度

  2. 密码长度 < 信息长度

对于第一种情况，直接把路径上的所有节点的 end 累加即可。

对于第二种情况，可以考虑再增加一个 cnt 计数器表示有多少条信息经过这个节点。然后在密码的末尾节点处不加 end 而是加 cnt。

看代码理解吧：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int son[2],cnt,end;
}t[500001];//字典树
int a[10001],n,m,len,tot=1;
void add(int now,int x){//now 表示当前节点编号，x表示当前信息的编号
    if(x>len)return;//长度溢出
    if(t[now].son[a[x]])now=t[now].son[a[x]];//有孩子则跳转
    else{//新建立子节点
        t[now].son[a[x]]=++tot;//tot为当前节点数量
        t[tot].son[0]=t[tot].son[1]=0;
        now=tot;
    }
    t[now].cnt++;//累加cnt
    if(x==len)t[now].end++;//最末尾则累加end
    add(now,x+1);//进入下一层
}
void query(int now,int x,int ans){//ans表示最终答案，其余同上
    if(t[now].son[a[x]])now=t[now].son[a[x]];
    else{//此时密码长度较长，无法继续访问，进入情况1
        printf("%d\n",ans);
        return;
    }
    if(x==len){//密码遍历完，长度较短，进入情况2
        printf("%d\n",ans+t[now].cnt);
        return;
    }
    ans+=t[now].end;//ans累加
    query(now,x+1,ans);
}
int main(){
    scanf("%d%d",&m,&n);
    while(m--){
        scanf("%d",&len);
        for(int i=1;i<=len;i++)scanf("%d",a+i);
        add(1,1);//处理end、ans
    }
    while(n--){
        scanf("%d",&len);
        for(int i=1;i<=len;i++)scanf("%d",a+i);
        query(1,1,0);//查询答案
    }
    return 0;
}

完结撒花！