(Luogu) P2922 [USACO08DEC]秘密消息Secret Message (字典树)

本文主要是介绍(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 (字典树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---