本文主要是介绍(Luogu) P2922 [USACO08DEC]秘密消息Secret Message (字典树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
传送门
解题思路:查询前缀的个数,典型的字典树问题(字典树入门和例题),给你一个前缀,如果单词(都称为单词了)与这个前缀的前部分重合时,res也++,这是需要注意的,例如:前缀10111,那么101也算一个答案;用一个sum数组记录到root这个点为前缀个数,同时flag数组为以root为结尾的单词的个数(flag从标记结尾,变成个数,因为可能有相同的单词数),查询前缀时,遇到flag不为0,那就说明有以这个节点为结尾的单词,加上;如果前缀到了 !tree[root][id] (说明没有单词到这)的点,那就返回res,反之,前缀走完,res+sum[root],但是如果root恰为一个单词的结尾,那res要减去flag[root],因为和sum[root]重复了。(用的vector 偷懒了,最好用数组比较快)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=2e6+5;
int tree[maxn][3],tot=0,sum[maxn];
int flag[maxn];
vector<int> a;
int n,m;
inline void add(vector<int> s){int root=0,id,len=s.size();for(int i=0;i<len;++i){id=s[i];if(!tree[root][id]) tree[root][id]=++tot;root=tree[root][id];sum[root]++;}flag[root]++;
}
inline int find(vector<int> s){int root=0,id,len=s.size(),res=0;for(int i=0;i<len;++i){id=s[i];if(!tree[root][id]){return res;} root=tree[root][id];if(flag[root]) res+=flag[root];} res+=sum[root];if(flag[root]) res-=flag[root];return res;
}
int main(){std::ios::sync_with_stdio(0);cin>>n>>m;int num,tp;for(int i=0;i<n;++i){cin>>num;for(int j=0;j<num;++j){cin>>tp;a.push_back(tp);}add(a);a.clear();}for(int i=0;i<m;++i){cin>>num;int ans=0;for(int j=0;j<num;++j){cin>>tp;a.push_back(tp);}cout<<find(a)<<endl;a.clear();}return 0;
}
这篇关于(Luogu) P2922 [USACO08DEC]秘密消息Secret Message (字典树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!