题目描述

贝茜正在领导奶牛们逃跑.为了联络,奶牛们互相发送秘密信息.

信息是二进制的,共有 $M$($1$ $\le$ $M$ $\le$ $50000$)条,反间谍能力很强的约翰已经部分拦截了这些信息,知道了第 $i$ 条二进制信息的前 $b_i$($1$ $\le$ $b_i$ $\le$ $10000$)位,他同时知道,奶牛使用 $N$($1$ $\le$ $N$ $\le$ $50000$)条暗号.但是,他仅仅知道第 $j$ 条暗号的前 $c_j$($1$ $\le c_j$ $\le 10000$)位。

对于每条暗号 $j$,他想知道有多少截得的信息能够和它匹配。也就是说,有多少信息和这条暗号有着相同的前缀。当然,这个前缀长度必须等于暗号和那条信息长度的较小者。

在输入文件中,位的总数(即 $\sum b_i + \sum c_i$)不会超过 $500000$。

输入格式

第$1$行,两个整数 $M$ 和 $N$。

第$2...M+1$行:每行一个整数 $b_i$,后跟 $b_i$ 个整数10描述一条信息。

第$M+2...M+N+1$行:每行一个整数 $c_j$ ,后跟$c_j$个整数10描述一条暗号。

输出格式

第$1...M$行:第$j$行输出能和第$j$条暗号匹配的信息数量。

输入输出样例

输入 #1

4 5 
3 0 1 0 
1 1 
3 1 0 0 
3 1 1 0 
1 0 
1 1 
2 0 1 
5 0 1 0 0 1 
2 1 1 3
4 2 3 1 10 5 9 7

输出 #1

1 
3 
1 
1 
2 

分析

分析题意可知,题目给定$M$个二进制数组,依次给出一个二进制数组求这个二进制数组与给定的$M$个二进制数组拥有相同前缀的数量,可知算法核心为统计前缀,应使用Trie

对给定的$M$个二进制数组进行建Trie,在建Trie经过的路径上的每一节点增加一个$sum$来表示经过这个节点的给定数组的数量,在每一个数组的末尾节点增加一个$end$来表示在这个节点结束的给定数组的数量。

查询前缀数量时有两种情况:

  1. 与数组有相同前缀的给定数组的长度均不大于数组长度:此时只需要统计查询路径上的$end$和,即可表示所有与数组有相同前缀的给定数组的数量。
  2. 有至少一个与数组有相同前缀的给定数组的长度大于数组长度:此时所有与数组有相同前缀的给定数组有两部分——小于数组长度和不小于数组长度的,此时所有与数组有相同前缀的给定数组的数量为查询路径上的$end$和减去数组末尾节点的$end$再加上减去数组末尾节点的$sum$。

代码

#include<bits/stdc++.h>
using namespace std;
int m,n,ans;
int len,a[10001];
int sum[500050],end[500050];
int node[500050][2];
int size=1,flag;
void insert(int cur,int dep){
    if(dep>len){
        end[cur]++;
        return;
    }
    if(node[cur][a[dep]]==0){
        node[cur][a[dep]]=++size;
        sum[node[cur][a[dep]]]++;
        insert(node[cur][a[dep]],dep+1);
    }else{
        sum[node[cur][a[dep]]]++;
        insert(node[cur][a[dep]],dep+1);
    }
}
void search(int cur,int dep){
    if(dep>len){
        printf("%d\n",ans-end[cur]+sum[cur]);
        return;
    }
    cur=node[cur][a[dep]];
    ans+=end[cur];
    if(cur)search(cur,dep+1);
    else{
        printf("%d\n",ans);
        return;
    }
    
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        scanf("%d",&len);
        for(int j=1;j<=len;j++){
            scanf("%d",&a[j]);
        }
        insert(1,1);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&len);
        for(int j=1;j<=len;j++){
            scanf("%d",&a[j]);
        }
        ans=0;
        search(1,1);
    }
    return 0;
}
最后修改:2021 年 07 月 03 日 07 : 40 PM
如果觉得我的文章对你有用,请随意赞赏