| ||||||||||
| 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