于是她不当的点名初阶了

P2580 于是她不当的点名初阶了

标题背景

XS中学化学竞技组教练是一个青睐炉石的人。

他会一边搓炉石一边点名以至于有一天她接二连三点到了有个别同学三回,然后正好被路过的校长意识了接下来正是一顿欧拉欧拉欧拉(详情请见已告竣竞赛CON900)。

题目叙述

那之后校长任命你为打发探员,每日记录她的点名。校长会提供化学比赛学生的总人口和名单,而你供给报告校长他有没有点错名。(为何不直接不让他玩炉石。)

输入输出格式

输入格式:

 

先是行3个平头 n,表示班上人数。接下来 n
行,每行2个字符串表示其名字(相差十分大,且只含小写字母,长度不当先50)。第 n+2 行3个整数 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地图