Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
献上数组写法 141MS//3208K 141MS #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define clr( a , x ) memset ( a , x , sizeof (a) ); #define RE freopen("in.txt","r",stdin); #define WE freopen("out.txt","w",stdout); const int maxn = 10000 * 13 + 5; const int maxch = 11; struct tree { int next[maxn][maxch]; bool leaf[maxn]; int cnt, root; int newNode() { memset(next[cnt], -1, sizeof(next[cnt])); return cnt++; } void init() { cnt = 0; root = newNode(); memset(leaf, false, sizeof(leaf)); } bool insert(char *s1) { int len = strlen(s1); int cur = root; for (int i = 0; i < len; ++i) { int id = s1[i] - '0'; if (next[cur][id] == -1) { next[cur][id] = newNode(); } if (leaf[cur]) return true; cur = next[cur][id]; } leaf[cur] = true; //如果当前串后面还有则说明该串是某串的前缀 for (int i = 0; i < maxch; ++i){ if(next[cur][i] != -1) return true; } return false; } } trie; int main() { // RE int t, n; char s1[12]; scanf("%d", &t); while (t--) { scanf("%d", &n); bool done = false; trie.init(); for (int i = 0; i < n; ++i) { scanf("%s", s1); if (trie.insert(s1)) { done = true;} } if (done) printf("NO\n"); else printf("YES\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator