PDF
虽然我很想说这是一道字典树模板题，但是还是有点技巧的。
对于每组输入，我们先把它存入字典树，然后再来查找（也就是所谓的离线）
为了说明方便，用表格说明一下变量吧
| 变量名 |
变量作用 |
| st |
保存读入的字符串，用于离线 |
| word |
保存字典树每条边被覆盖的次数，遍历时为1说明不是前缀 |
| ch |
字典树，第一维是编号，第二维是哪条边，值为指向的点 |
| sz |
用来编号，类似于链式前向星里的tot |
关键是遍历的时候，只要word为1就返回0（就是它自己啊），能顺利的走下来就返回1
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 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAX = 1e5 + 10; int t,n; char st[10100][10]; int word[MAX],ch[MAX][10],sz; void reset(){//每组数据需要重置 sz = 1; memset(ch[0],0,sizeof(ch[0])); memset(word,0,sizeof(word)); } void insert(char *s){//插入进字典树 int nl = strlen(s),u = 0; for(int i = 0 ; i < nl ;i++){ int c = s[i] - '0'; if(! ch[u][c]){ memset(ch[sz],0,sizeof(ch[sz])); ch[u][c] = sz++; } u = ch[u][c]; word[u]++; } } int find(char *s){//是否是前缀 int nl = strlen(s),u = 0; for(int i = 0; i < nl; i++){ int c = s[i] - '0'; u = ch[u][c]; if(word[u] == 1) return 0; } return 1; } int main(){ cin>>t; while(t--){ reset(); scanf("%d",&n); for(int i = 1 ; i <= n; i++){ scanf("%s",st[i]); insert(st[i]); } int ok = 1; for(int i = 1 ; i <= n; i++) if(find(st[i])){ ok = 0; break; } if(ok) printf("YES\n"); else printf("NO\n"); } return 0; } |
