本文共 3262 字,大约阅读时间需要 10 分钟。
题目背景
XS中学化学竞赛组教练是一个酷爱炉石的人。 他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次,然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉(详情请见已结束比赛 CON900)。题目描述
这之后校长任命你为特派探员,每天记录他的点名。校长会提供化学竞赛学生的人数和名单,而你需要告诉校长他有没有点错名。(为什么不直接不让他玩炉石。)输入格式
第一行一个整数 n n n ,表示班上人数。接下来 n n n 行,每行一个字符串表示其名字(互不相同,且只含小写字母,长度不超过 50 50 50 )。 第 n + 2 n+2 n+2 行一个整数 m m m ,表示教练报的名字个数。接下来 m m m 行,每行一个字符串表示教练报的名字(只含小写字母,且长度不超过 50 50 50 )。输出格式
对于每个教练报的名字,输出一行。 如果该名字正确且是第一次出现,输出OK
,如果该名字错误,输出 WRONG
,如果该名字正确但不是第一次出现,输出 REPEAT
。 输入输出样例
输入 #15 abcadacd3aae
输出 #1
OKREPEATWRONG
说明/提示
- 对于 40 % 40\% 40% 的数据, n ≤ 1000 , m ≤ 2000 n\le 1000,m\le 2000 n≤1000,m≤2000 。
- 对于 70 % 70\% 70% 的数据, n ≤ 1 0 4 , m ≤ 2 × 1 0 4 n\le 10^4,m\le 2\times 10^4 n≤104,m≤2×104 。
- 对于 100 % 100\% 100% 的数据, n ≤ 1 0 4 , m ≤ 1 0 5 n\le 10^4,m≤10^5 n≤104,m≤105 。
题意:点名看是否点对、点错或者重复。
思路1:用 map
存储输入的字符串,map<string, bool>
。开始时都没有被点到,于是都是 false
。点到后改为 true
,如果点错,就输出 WRONG
。代码如下:
#includeusing 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; }};mapmapStr; 再使用就可以了。但是需要注意,实际记录的仍是
char*
地址到int
的映射,只是查询时变为了char*
内容的大小比较,所以当键char*
地址对应的内容发生变化时,也就相当于mapStr
对应的键内容发生变化。故在使用时,需将mapStr
的键值绑定到内容不会变化的地址。
思路2:使用静态字典树。每次输入字符串时,将其插入到字典树中。查询某个字符串是否存在,可以使用另一个 bool exist[]
数组(作为 int ends[]
的替代)。在插入完成时,将 exist[叶子节点] = true
。然后按照查询前缀的方法查询,在结尾处判断一下 exist
的值即可。这是一种常见的做法,用叶子结点代表整个字符串,保存某些信息,线段树中也会使用这种套路。
如何判断重复点名?只需要另外加一个 vis
数组就可以了,第一次查询成功后将叶子结点的 vis
设置为 true
即可。
代码如下:
#includeusing 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; }
提交:
转载地址:https://memcpy0.blog.csdn.net/article/details/108305670 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!