Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给出n个字符串，问是否满足所有的字符串都不以其他的字符串为前缀。
思路：字典树，先建树，然后每次查找的之前先删掉自己，找完以后再加回来。
以及这题动态建艹不过。。。学习了一下静态建树的写法。。。第一次写静态的写法。。。可以当做模板用。。。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月16日 星期二 00时46分23秒
4File Name :code/poj/3630.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n;
35char s[N][12];
36int tot;
37struct Trie
38{
39 int nxt[10];
40 int cnt;
41
42 void init()
43 {
44 ms(nxt,0);
45 cnt = 0;
46 }
47}trie[N];
48int add()
49{
50 memset(&trie[tot],0,sizeof(Trie));
51 return tot++;
52}
53void Insert(char *s)
54{
55 int rt = 0 ;
56 int len = strlen(s);
57 for ( int i = 0 ; i < len ; i++)
58 {
59 int v = s[i]-'0';
60 if (!trie[rt].nxt[v]) trie[rt].nxt[v] = add();
61 rt = trie[rt].nxt[v];
62 trie[rt].cnt++;
63 }
64}
65void Delete(char *s)
66{
67 int rt = 0 ;
68 int len = strlen(s);
69 for ( int i = 0 ; i < len ; i++)
70 {
71 int v = s[i]-'0';
72 if (trie[rt].nxt[v])
73 {
74 rt = trie[rt].nxt[v];
75 trie[rt].cnt--;
76 }
77 }
78}
79bool Find(char *s)
80{
81 int rt = 0 ;
82 int len = strlen(s);
83 for ( int i = 0 ; i < len ;i++)
84 {
85 int v = s[i]-'0';
86 if (!trie[rt].nxt[v]||trie[trie[rt].nxt[v]].cnt==0) return false;
87 rt = trie[rt].nxt[v];
88 }
89 return true;
90}
91int main()
92{
93 #ifndef ONLINE_JUDGE
94 freopen("code/in.txt","r",stdin);
95 #endif
96 int T ;
97 cin>>T;
98 while (T--)
99 {
100 scanf("%d",&n);
101 tot = 1;
102 trie[0].init();
103 for ( int i = 1 ; i <= n ; i++)
104 {
105 scanf("%s",s[i]);
106 // cout<<"s[i]:"<<s[i]<<endl;
107 Insert(s[i]);
108 }
109 bool ok = true;
110 for ( int i = 1 ; i <= n ; i++)
111 {
112 Delete(s[i]);
113 if (Find(s[i]))
114 {
115 ok = false;
116 break;
117 }
118 Insert(s[i]);
119 }
120 if (ok)
121 {
122 puts("YES");
123 }
124 else
125 {
126 puts("NO");
127 }
128 }
129 #ifndef ONLINE_JUDGE
130 fclose(stdin);
131 #endif
132 return 0;
133}