当前位置: 代码迷 >> 综合 >> P2922 [USACO08DEC]Secret Message G (字典树 trie)
  详细解决方案

P2922 [USACO08DEC]Secret Message G (字典树 trie)

热度:53   发布时间:2023-12-05 21:41:51.0

[USACO08DEC]Secret Message G - 洛谷

题意

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

信息是二进制的,共有 MM(1 \le M \le 500001≤M≤50000)条,反间谍能力很强的约翰已经部分拦截了这些信息,知道了第 ii 条二进制信息的前 b_ibi?(l \le b_i \le 10000l≤bi?≤10000)位,他同时知道,奶牛使用 NN(1 \le N \le 500001≤N≤50000)条暗号.但是,他仅仅知道第 jj 条暗号的前 c_jcj?(1 \le c_j \le 100001≤cj?≤10000)位。

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

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

输入输出样例

输入

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 

输出

1 
3 
1 
1 
2 

题解:

典型的字典树统计题。

建树,在这串数列中走过的路径中的sum+1,num代表有num个串经过这个节点。

当一个串插完以后,在当前节点(即该串的最后一个数字)的cnt上+1,cnt代表有cnt个串在这个节点终结。

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

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

如果完全走到尾,就减cnt,加num,意为加上以该串为前缀的数量,同时减掉刚好一模一样的串。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);inline int read()
{int x=0,k=1; char c=getchar();while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;
}
const int maxn=1e6+10;
int n,m,k,tot,num[maxn],cnt[maxn];
int tre[maxn][2];
char s[maxn];
bool f=1;
void _add(char s[],int len){int now=0;for(int i=0;i<len;i++){int tep=s[i]-'0';if(!tre[now][tep]){tre[now][tep]=++tot;}now=tre[now][tep];num[now]++;}cnt[now]++;return;
}
int ask(char s[],int len){int now=0,ans=0;for(int i=0;i<len;i++){int tep=s[i]-'0';if(tre[now][tep]) {now=tre[now][tep];ans+=cnt[now];}else break;if(i==len-1){ans+=num[now]-cnt[now];break;}}return ans;
}
signed main(){fastm=read();n=read();for(int i=1;i<=m;i++){k=read();for(int i=0;i<k;i++) s[i]=read();_add(s,k); 	}for(int i=1;i<=n;i++){k=read();for(int i=0;i<k;i++) s[i]=read();printf("%lld\n",ask(s,k));}
}

  相关解决方案