题目背景
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% 的数据, n1000,m2000;
对于 70% 的数据, n10000,m20000;
对于 100% 的数据, n10000,m100000.
第一眼就觉得是 hash, 写完一丢上去, RE??, 开大数组减小 base 再来一遍, RE??, 再来一遍....... 终于, 在第七遍 RE 后, 我发现事情并不简单, 下了个数据看看, 明明自己机子上都能过, wtf??, 被逼无奈下掏出 trie 树
先介绍一手 trie 树
trie 树, 中文名字典树 (没错用英文只是为了装逼), 先看张图
(以上来自百度)
除了根节点外 (为什么等下会说), 字典树中的每一个节点都代表一个字母, 对任意一颗子树进行遍历都可以得到一个串, 如上图, 从最左边一路遍历下去, 依次经过 a,d,d 或 a,m; 可以得到 add 这个串或者 am 这个串, 那如果我有一个 ad 的串该怎么办呢, 这里引入一个标记, 例如有一个串 ad, 在构建字典树时, 我就对 d 这个节点打一个标记, 表示从开头遍历到当前节点是一个串
对于一个 trie[i][j] 表示从 i 出发到 i 的第 j 棵子树, 那如何区分呢, 我们规定一下两个值
第一个, 是进入 trie 的顺序, 此时相同字符的值可能不同
第二个, 是节点子树的值, 此时相同字符的值一定相同 (看不懂的话下面会结合代码讲)
介绍下 trie 的两个基本操作: add 和 find
- add
- char ch[MAXN];//ch 为待处理数组
- void add()
- {
- int len=strlen(ch),rt=0;// 获取长度, 根节点为 0
- for(int i=0;i<len;i++)
- {
- int k=ch[i]-'a';// 第二个标记, k 代表的是节点子树对应的值
- if(!trie[rt].son[k])// 如果没有这个节点
- trie[rt].son[k]=++tot;// 第一个标记, tot 的值即为进入 trie 的顺序
- rt=trie[rt].son[k];// 向下走
- }
- trie[rt].have=1;// 结束时打上一个标记, 表示到目前是一个串
- }
- find
- int find()
- {
- int len=strlen(ch),rt=0;
- for(int i=0;i<len;i++)
- {
- int k=ch[i]-'a'; // 前面的基本一样
- if(!trie[rt].son[k])return 3;// 如果走不下去了, 说明没有这个串, 返回 3, 表示没有
- rt=trie[rt].son[k]; // 向下走
- }
- if(!trie[rt].have)return 3;// 如果没有标记, 说明没有这个串, 返回 3, 表示没有
- if(!trie[rt].cnt)// 如果第一次访问
- {
- trie[rt].cnt++;
- return 1;// 返回 1, 表示第一次出现
- }
return 2; 否则返回 2, 表示出现过了
}
完整代码
- #include<bits/stdc++.h>
- using namespace std;
- const int MAXN=10+1e6;
- struct node{
- int son[27];
- bool have;
- int cnt;
- }trie[MAXN];
- int n,tot;
- char ch[MAXN];
- void add()
- {
- int len=strlen(ch),rt=0;
- for(int i=0;i<len;i++)
- {
- int k=ch[i]-'a';
- if(!trie[rt].son[k])
- trie[rt].son[k]=++tot;
- rt=trie[rt].son[k];
- }
- trie[rt].have=1;
- }
- int find()
- {
- int len=strlen(ch),rt=0;
- for(int i=0;i<len;i++)
- {
- int k=ch[i]-'a';
- if(!trie[rt].son[k])return 3;
- rt=trie[rt].son[k];
- }
- if(!trie[rt].have)return 3;
- if(!trie[rt].cnt)
- {
- trie[rt].cnt++;
- return 1;
- }
- return 2;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%s",ch);
- add();
- }
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%s",ch);
- int k=find();
- if(k==1)
- cout<<"OK"<<endl;
- if(k==2)
- cout<<"REPEAT"<<endl;
- if(k==3)
- cout<<"WRONG"<<endl;
- }
- return 0;
- }
附赠蜜汁 RE 的 hash
- #include<bits/stdc++.h>
- using namespace std;
- const int MAXN=105;
- struct node{
- int son[MAXN];
- bool have;
- int cnt;
- }trie[MAXN];
- int n,tot;
- char ch[MAXN];
- void add()
- {
- int len=strlen(ch),rt=0;
- for(int i=0;i<len;i++)
- {
- int k=ch[i]-'a';
- if(!trie[rt].son[k])
- trie[rt].son[k]=++tot;
- rt=trie[rt].son[k];
- }
- trie[rt].have=1;
- }
- int find()
- {
- int len=strlen(ch),rt=0;
- for(int i=0;i<len;i++)
- {
- int k=ch[i]-'a';
- if(!trie[rt].son[k])return 3;
- rt=trie[rt].son[k];
- }
- if(!trie[rt].have)return 3;
- if(!trie[rt].cnt)
- {
- trie[rt].cnt++;
- return 1;
- }
- return 2;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%s",ch);
- add();
- }
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%s",ch);
- int k=find();
- if(k==1)
- cout<<"OK"<<endl;
- if(k==2)
- cout<<"REPEAT"<<endl;
- if(k==3)
- cout<<"WRONG"<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2698870.html