于是他错误的点名开始了

GitHub跳转原题关系图返回列表

分别用合法姓名集合和已点名集合区分 WRONG、OK 与 REPEAT。

OJ: luogu

题目 ID: P2580

难度:普及-

标签:集合字符串状态记录python

日期: 2026-07-16 19:57

后置题目
luogu P1481魔族密码集合查重作为 Trie 的简单铺垫

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

每次读到一个姓名：不在名单输出 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)O(1)。
  • 答案列表最后用换行连接，避免频繁输出。

代码

python
import 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))

复杂度

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

总结

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