题解

思路

需要同时完成名单成员查询和“是否已经点过”的状态记录。规模增大时，依次使用线性扫描、排序后二分和 Trie 降低单次查询复杂度。

做法

子任务一

每次点名顺序扫描学生名单，找到对应编号后检查该编号是否已经出现。复杂度为 $O(nmL)$。

子任务二

先将名单按字典序排序。每次点名二分查找名字，并按排序后的位置记录是否已经出现。复杂度为 $O((n+m)L\log n)$。

子任务三

把所有名字插入 Trie，终止节点记录学生编号。查询时沿字符边行走；无法走到终止节点则输出 WRONG，首次到达未标记终止节点输出 OK 并标记，再次到达则输出 REPEAT。

正确性证明

Trie 中从根到终止节点的路径与名单中的一个完整名字一一对应。因此查询无法到达终止节点时，名字不在名单中；到达终止节点时，名字确为某位学生。每个终止节点的标记仅在第一次正确点名时由未标记变为已标记，所以第一次输出 OK，其后始终输出 REPEAT。三种输出与题意完全一致。

复杂度分析

设所有输入名字的总字符数为 $S$。建 Trie 和全部查询的时间复杂度为 $O(S)$，空间复杂度为 $O(S)$。