洛谷P2922 [USACO08DEC]Secret Message G 题解
题目链接:P2922 [USACO08DEC]Secret Message G
题意:
一句话题意:\(m\) 次询问,查询已有的 \(n\) 个 \(\tt{01}\) 串中,有多少串 \(t_i\) 能使询问串 \(s\) 成为其前缀。
贝茜正在领导奶牛们逃跑.为了联络,奶牛们互相发送秘密信息.
信息是二进制的,共有 \(M\)(\(1 \le M \le 50000\))条,反间谍能力很强的约翰已经部分拦截了这些信息,知道了第 \(i\) 条二进制信息的前 \(b_i\)(\(l \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\)。
考虑建 \(\tt{trie}\) 树处理
没了,就这么简单。
具体见代码,有一些小的细节要注意
时间复杂度 \(O(\sum b_i + M \sum c_i)\)
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)
string str;
int n,m,k,tot;
struct Trie
{
int trie[N][2],ed[N],sum[N];
void insert(int l)
{
int u=0;
for(int i=1,c; i<=l; i++)
{
cin >> c;
if(!trie[u][c])trie[u][c]=++tot;
++sum[u=trie[u][c]];
}
++ed[u];
}
int query(int l)
{
int u=0,ok=1,res=0;
for(int i=1,c; i<=l; i++)
{
cin >> c;
if(!trie[u][c])
{
while(++i<=l) cin >> c;
return res;
};
res+=ed[u=trie[u][c]];
}
return res-ed[u]+sum[u]; // ed[u]是sum[u]的子集
}
}tr;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i=1,x; i<=n; i++)
{
cin >> x;
tr.insert(x);
}
for(int i=1,x; i<=m; i++)
{
cin >> x;
cout << tr.query(x) << '\n';
}
return 0;
}