洛谷 P2580 于是他错误的点名开始了

题目背景

XS中学化学竞赛组教练是一个酷爱炉石的人。

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

题目描述

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

输入格式

第一行一个整数 n，表示班上人数。

接下来 n 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 50）。

第 n+2 行一个整数 m，表示教练报的名字个数。

接下来 m 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 50）。

输出格式

对于每个教练报的名字，输出一行。

如果该名字正确且是第一次出现，输出OK，如果该名字错误，输出WRONG，如果该名字正确但不是第一次出现，输出REPEAT。

输入输出样例

输入 #1复制

5 a b c ad acd 3 a a e

输出 #1复制

OK REPEAT WRONG

说明/提示

• 对于 40% 的数据，n≤1000，m≤2000。
• 对于 70% 的数据，n≤104，m≤2×104。
• 对于 100% 的数据，n≤104，m≤105。

---

upd 2022.7.30：新增加一组 Hack 数据。

#include<bits/stdc++.h> using namespace std; const int N=5e5 + 10; //字典序 int e[N]; int tr[N][26]; int idx; int n,m; void insert(string& s) { int cur=0; for(auto ch:s) { int path=ch-'a'; if(tr[cur][path]==0) tr[cur][path]=++idx; cur=tr[cur][path]; } e[cur]++; } int find_all(string& s) { int cur =0; for(auto ch: s) { int path=ch-'a'; if(tr[cur][path]==0) return 0; cur=tr[cur][path]; } if(e[cur]>0) { int t=e[cur]; e[cur]=-1; return t; } return e[cur]; } int main() { scanf("%d",&n); string s; while(n--) { cin>>s; insert(s); } cin>>m; while(m--) { cin>>s; int node=find_all(s); if (node == 0) { printf("WRONG\n"); } else if (node >0) { printf("OK\n"); } else { printf("REPEAT\n"); } } return 0; }