洛谷 P2580 于是他错误的点名开始了 & 【模板】trie树（字典树）

传送门

解题思路

当然可以map水过（map大法好）

字典树也就是板子的插入查询操作。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn=10005;
 6 int ch[55*maxn][30],cnt;
 7 int vis[maxn*55],n,m;
 8 string s;
 9 void insert(string s){
10     int len=s.length();
11     int now=1;
12     for(int i=0;i<len;i++){
13         if(!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++cnt;
14         now=ch[now][s[i]-'a'];
15     }
16     vis[now]=1;
17 }
18 void query(string s){
19     int len=s.length();
20     int now=1;
21     for(int i=0;i<len;i++){
22         if(!ch[now][s[i]-'a']){
23             printf("WRONG
");
24             return;
25         }
26         now=ch[now][s[i]-'a'];
27     }
28     if(vis[now]==0) printf("WRONG
");
29     if(vis[now]==1) printf("OK
");
30     if(vis[now]>=2) printf("REPEAT
");
31     vis[now]++;
32 }
33 int main(){
34     cin>>n;
35     for(int i=1;i<=n;i++){
36         cin>>s;
37         insert(s);
38     }
39     cin>>m;
40     for(int i=1;i<=m;i++){
41         cin>>s;
42         query(s);
43     }
44     return 0;
45 }