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