洛谷 P3879 [TJOI2010]阅读理解（trie树）

传送门

解题思路

普通的trie貌似会MLE

但是我们可以偷偷数组少开个零，就A了

想知道为什么？

别问，问就是数据水。

其实正解map bitset等等……

看来以后要学学bitset……

AC代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<iomanip>
 5 #include<cmath>
 6 #include<set>
 7 using namespace std;
 8 const int maxn=500005;
 9 int n,m,nn,cnt=1,ch[maxn][26];
10 set<int> vis[maxn];
11 string s;
12 void insert(int id){
13     int len=s.length(),now=1;
14     for(int i=0;i<len;i++){
15         if(!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++cnt; 
16         now=ch[now][s[i]-'a'];
17     }
18     vis[now].insert(id);
19 }
20 void query(){
21     int len=s.length(),now=1;
22     for(int i=0;i<len;i++){
23         if(!ch[now][s[i]-'a']){
24             cout<<endl;
25             return;
26         }
27         now=ch[now][s[i]-'a'];
28     }
29     if(vis[now].empty()) cout<<endl;
30     else{
31         for(set<int>::iterator i=vis[now].begin();i!=vis[now].end();i++) cout<<(*i)<<" ";
32         cout<<endl;
33     }
34 }
35 int main(){
36     cin>>n;
37     for(int i=1;i<=n;i++){
38         cin>>nn;
39         for(int j=1;j<=nn;j++){
40             cin>>s;
41             insert(i);
42         }
43     }
44     cin>>m;
45     for(int i=1;i<=m;i++){
46         cin>>s;
47         query();
48     }
49     return 0;
50 }