于是他错误的点名开始了

题目背景

XS中学化学竞赛组教练是一个酷爱炉石的人。

他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉（详情请见已结束比赛CON900）。

题目描述

这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么不直接不让他玩炉石。）

输入输出格式

输入格式：

第一行一个整数 n，表示班上人数。接下来 n 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 50）。第 n+2 行一个整数 m，表示教练报的名字。接下来 m 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 50）。

输出格式：

对于每个教练报的名字，输出一行。如果该名字正确且是第一次出现，输出“OK”，如果该名字错误，输出“WRONG”，如果该名字正确但不是第一次出现，输出“REPEAT”。（均不加引号）

输入输出样例

输入样例#1：

5  
a
b
c
ad
acd
3
a
a
e

输出样例#1：

OK
REPEAT
WRONG

说明

对于 40%的数据，n≤1000,m≤2000；

对于 70%的数据，n≤10000,m≤20000；

对于 100%的数据， n≤10000，m≤100000。

T1总是送分的。

思路：STL_map||字典树

代码实现：

STL_map：

 1 #include<map>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 map<string,int> name;
 7 int n,m,l;
 8 string ch;
 9 int main(){
10     scanf("%d",&n);
11     for(int i=0;i<n;i++){
12         cin>>ch;
13         name[ch]=1;
14     }
15     scanf("%d",&m);
16     for(int i=0;i<m;i++){
17         cin>>ch;
18         if(name[ch]==2){printf("REPEAT
");}
19         if(name[ch]==1){++name[ch];printf("OK
");}
20         if(name[ch]==0){printf("WRONG
");}
21     }
22     return 0;
23 }

字典树：

 1 #include<cstdio>
 2 #include<cstring>
 3 #define nt j+ch[i]-'a'
 4 int n,m,l,ss;
 5 char ch[60];
 6 int s[10000000];
 7 bool v[10000000];
 8 void put(int l){
 9     for(int i=0,j=0;i<l;i++){
10         if(!s[nt]) s[nt]=ss+26,ss+=26;
11         j=s[nt];
12     }
13 }
14 void find(int l){
15     for(int i=0,j=0;i<l;i++)
16     if(!s[nt]){puts("WRONG");return;}
17     else ss=j=s[nt];
18     if(v[ss]) puts("REPEAT");
19     else puts("OK"),v[ss]=1;
20 }
21 int main(){
22     ss=26;
23     scanf("%d",&n);
24     for(int i=1;i<=n;i++){
25         scanf("%s",ch);
26         put(strlen(ch));
27     }
28     scanf("%d",&m);
29     for(int i=1;i<=m;i++){
30         scanf("%s",ch);
31         find(strlen(ch));
32     }
33     return 0;
34 }

题目来源：洛谷