于是她不当的点名开始了

P2580 于是他不当的点名开首了

题材背景

XS中学化学比赛组教练是贰个热爱炉石的人。

她会1边搓炉石一边点名以至于有1天他接连点到了某些同学一遍,然后正好被路过的校长意识掌握后就是①顿欧拉欧拉欧拉(详情请见已告竣竞赛CON900)。

题材叙述

这之后校长任命你为打发探员,每一天记下她的点名。校长会提供化学竞技学生的人头和名单,而你须求报告校长他有未有点错名。(为何不直接不让他玩炉石。)

化学答案,输入输出格式

输入格式:

 

第三行四个整数 n,表示班上人数。接下来 n
行,每行3个字符串表示其名字(大相径庭,且只含小写字母,长度不超越50)。第 n+2 行1个平头 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总是送分的。

code

输出 注意分寸写!!!

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 500100
 4 
 5 struct Trie
 6 {
 7     int ch[MAXN][26];
 8     int val[MAXN];
 9     int size;
10     Trie()
11     {
12         size = 1;
13         memset(ch,0,sizeof(ch));
14         memset(val,0,sizeof(val));
15     }
16     int id(char c)
17     {
18         return c-'a';
19     }
20     void Ins(char* s)
21     {
22         int u = 0, len = strlen(s);
23         for (int i=0; i<len; ++i)
24         {
25             int c = id(s[i]);
26             if (!ch[u][c]) ch[u][c] = size++;
27             u = ch[u][c];
28         }
29         val[u] = 1;
30     }
31     int Find(char* s)
32     {
33         int u = 0, len = strlen(s);
34         for (int i=0; i<len; ++i)
35         {
36             int c = id(s[i]);
37             if (!ch[u][c]) return 0;
38             u = ch[u][c];
39         }
40         if (val[u]==1)
41         {
42             val[u] = 2;
43             return 1;
44         }
45         if (val[u]==2) return 2;
46         return 0;
47     }    
48 }t;
49 
50 int main()
51 {
52     int n,m,k;
53     char word[55];
54     scanf("%d",&n);
55     for (int i=1; i<=n; ++i)
56     {
57         scanf("%s",word);
58         t.Ins(word);
59     }
60     scanf("%d",&m);
61     for (int i=1; i<=m; ++i)
62     {
63         scanf("%s",word);
64         k = t.Find(word);
65         if (k==0) printf("WRONG\n");
66         else if (k==1) printf("OK\n");
67         else printf("REPEAT\n"); 
68     }
69     return 0;
70 }

 

admin

网站地图xml地图