| ||||||||||
| 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 | |||||||||
HDU能过,POJ跪了。求大牛指点数据。。附代码。#include<iostream>
#include<string>
using namespace std;
const int MAX = 1<<16;
int up;
struct Node
{
int c[11];
bool isword;
Node()
{
up++;
isword = false;
memset(c, 0, sizeof(c));
}
}trie[MAX];
struct Str
{
char s[15];
int l;
}str[MAX];
void trieBuild()
{
up = 0;
trie[0] = Node();
}
bool trieAdd(char s[])
{
bool flag=true;
int i, now = 0;
for(i = 0; s[i]; ++i)
{
int p = s[i]-'0';
if(trie[now].c[p] == 0)
{
trie[now].c[p] = up;
trie[up] = Node();
}
now = trie[now].c[p];
if(trie[now].isword==true) flag=false;
}
trie[now].isword = true;
return flag;
}
int cmp(const void* a,const void* b)
{
Str *c=(Str *)a;Str *d=(Str *)b;
return c->l>d->l;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
char s[15];
trieBuild();
for(int i=0;i<n;++i)
{
scanf("%s",str[i].s);
str[i].l=strlen(str[i].s);
}
qsort(str,n,sizeof(str[0]),cmp);
bool flag=true;
for(int i=0;i<n;++i)
{
if(false==trieAdd(str[i].s)) {flag=false;break;}
}
if(flag) printf("YES\n");
else printf("NO\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