于是他错误的点名开始了

题意

每次读到一个姓名：不在名单输出 WRONG，第一次点到合法姓名输出 OK，之后再次点到输出 REPEAT。

思路

维护两个集合：

valid：完整合法名单，始终不变；
called：已经正确点到过的姓名。

按 name not in valid、name in called 的顺序判断即可。只有输出 OK 时才加入 called，错误姓名重复出现仍然应输出 WRONG。

Python 知识

集合推导式 {next(data) for ...} 直接读取名单。
bytes 可作为集合键，不必为每个姓名解码成 Unicode 字符串。
set.add 记录已出现状态，平均复杂度 $O(1)$ 。
答案列表最后用换行连接，避免频繁输出。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25import sys

# 一次性读入全部输入，用迭代器依次取数
data = iter(sys.stdin.buffer.read().split())

# 读入 n 个姓名作为名单
n = int(next(data))
valid = {next(data) for _ in range(n)}  # 名单集合，O(1) 查询

# 处理 m 次点名
m = int(next(data))
called = set()    # 已点到过的姓名
answers = []      # 收集每次结果

for _ in range(m):
    name = next(data)
    if name not in valid:
        answers.append("WRONG")   # 不在名单中
    elif name in called:
        answers.append("REPEAT")  # 已经点过了
    else:
        called.add(name)
        answers.append("OK")      # 第一次点到

print("\n".join(answers))

STL 写法

用 map<string, int> 直接把姓名当键、状态当值：1 表示在名单里还没点过，2 表示已经点过。查询时用 find，返回 end() 就说明名字不在名单，输出 WRONG；命中且值为 1 时改成 2 并输出 OK；命中且值为 2 时输出 REPEAT。这里刻意不写 state[name]：下标访问会把没见过的姓名插进表里，默认值 0 反而把“不在名单”和“在名单未点名”混在一起。相比上面手写的 Trie，省掉了 26 叉的 trie 数组和 node_cnt 维护，代价是每次查询多 $O(\log n)$ 次字符串比较。

对应的 cppbook 章节：map：通过键找到对应的值

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 01:15
 * update_at: 2026-10-07 01:20
 */
// 这是 STL 写法：用 map<string, int> 建立“姓名 -> 状态”的对照表。
// 状态含义：1 表示在名单里且还没被点到，2 表示已经被点到过；
// 查询用 find，不用 state[name]，因为下标访问会把没见过的姓名插进表里，
// 那样就分不清“不在名单”和“在名单但没点过”。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

map<string, int> state; // state[name] 表示姓名 name 的状态：1 未点名，2 已点名

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        string name;
        cin >> name;
        state[name] = 1; // 名单里的姓名统一记成“未点名”
    }

    ll m;
    cin >> m;
    for (ll i = 1; i <= m; i++) {
        string name;
        cin >> name;

        // find 只查询、不插入：返回 end() 就说明这个名字根本不在名单里
        auto it = state.find(name);
        if (it == state.end()) {
            cout << "WRONG\n";
        } else if (it->second == 1) {
            it->second = 2; // 第一次点到合法姓名，标记成已点名
            cout << "OK\n";
        } else {
            cout << "REPEAT\n";
        }
    }

    return 0;
}

复杂度

设姓名总字符数为 $L$ ，期望时间和空间均为 $O(L)$ 。

总结

C++ 常把本题作为 Trie 模板；Python 中完整字符串集合就是更自然的等价数据结构。