本文共 3262 字，大约阅读时间需要 10 分钟。

题目背景

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

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

5  abcadacd3aae

输出 #1

OKREPEATWRONG

说明/提示

• 对于 $40\%$ 的数据，$n\le 1000，m\le 2000$ 。
• 对于 $70\%$ 的数据，$n\le 10^4，m\le 2\times 10^4$ 。
• 对于 $100\%$ 的数据，$n\le 10^4，m\le 10^5$ 。

题意：点名看是否点对、点错或者重复。

---

思路1：用 map 存储输入的字符串，map<string, bool> 。开始时都没有被点到，于是都是 false 。点到后改为 true ，如果点错，就输出 WRONG 。代码如下：

#include 
   
    using namespace std; int main() {
    	int n, m;	scanf("%d\n", &n);	char str[60];	unordered_map
    
      dict;	for (int i = 0; i < n; ++i) {
   		gets(str);			//记录每个学生的名字 		dict[str] = false;  //未被点名 	}	scanf("%d\n", &m);	for (int i = 0; i < m; ++i) {
   		gets(str);		if (dict.find(str) == dict.end())			printf("WRONG\n");		else if (dict[str] == false) {
   			dict[str] = true;			printf("OK\n");			}		else 			printf("REPEAT\n");	}    return 0;}
    
   

注意：一般来说，我们不会使用 map<char*,xxx> 来存储字符串，因为 char* 无法直接比较。这里能够存储 char* 是因为 char*->string 的隐式类型转换。如果实在要存储并以 char* 作为键，看一下这篇博客就可以了：。看懂下面一段就行：

由于使用 map<char *,int> 表示的是指针值到int的映射。而在实际使用中，我们经常想表示的是指针内容与int的映射，但是又不想使用 map<string,int> ，怎么办？ 可通过重载操作符实现：

struct ptrCmp {
    　　 bool operator() ( const char * s1, const char * s2 ) const {
    　　　　return strcmp( s1, s2 ) < 0;　　}};map
    
      mapStr;
    

再使用就可以了。但是需要注意，实际记录的仍是 char* 地址到 int 的映射，只是查询时变为了 char* 内容的大小比较，所以当键 char* 地址对应的内容发生变化时，也就相当于 mapStr 对应的键内容发生变化。故在使用时，需将 mapStr 的键值绑定到内容不会变化的地址。

---

思路2：使用静态字典树。每次输入字符串时，将其插入到字典树中。查询某个字符串是否存在，可以使用另一个 bool exist[] 数组（作为 int ends[] 的替代）。在插入完成时，将 exist[叶子节点] = true 。然后按照查询前缀的方法查询，在结尾处判断一下 exist 的值即可。这是一种常见的做法，用叶子结点代表整个字符串，保存某些信息，线段树中也会使用这种套路。

如何判断重复点名？只需要另外加一个 vis 数组就可以了，第一次查询成功后将叶子结点的 vis 设置为 true 即可。

代码如下：

#include 
   
    using namespace std; const int maxn = 5e5 + 10;int trie[maxn][26], cnt;bool exist[maxn], vis[maxn]; //存在exist,重复查询vis void init() {
   	memset(trie, -1, sizeof(trie));	memset(vis, false, sizeof(vis));	memset(exist, false, sizeof(exist));	cnt = 0;}void insert(char s[]) {
   	int cur = 0;	for (int i = 0; s[i]; ++i) {
   		int index = s[i] - 'a';		if (trie[cur][index] == -1)			trie[cur][index] = ++cnt;		cur = trie[cur][index];	}	exist[cur] = true; }int search(char s[]) {
   	int cur = 0;	for (int i = 0; s[i]; ++i) {
   		int index = s[i] - 'a';		if (trie[cur][index] == -1) 			return -1;					//表示不存在这个字符串 		cur = trie[cur][index];	}	if (exist[cur] == false) return -1; //表示不存在这个字符串 	if (vis[cur] == false) {
       		//表示存在这个字符串而且还没被点名		vis[cur] = true;				//记录被点名 		return 0;	}	return 1;							//被重复点名 }int main() {
   	int n, m;	scanf("%d\n", &n);	char str[60];	init();	while (n--) {
   		gets(str);		insert(str);	}	scanf("%d\n", &m);	while (m--) {
   		gets(str);		int flag = search(str);		if (flag == -1) printf("WRONG\n");		else if (flag == 0) printf("OK\n");		else printf("REPEAT\n");	}	return 0;	}
   

提交：

转载地址：http://zaotf.baihongyu.com/