题目：hdu1671
题意：寻找一个号码是否有前缀跟其他的号码一样
解答：动态建字典树（在hdu上能过，在poj上不能过）
注意：每次加入字符串的时候边加入要边判断！！！
每建完一个树都要释放内存！！！
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int sonnum = 10; int ok = 1; struct Trie { int num; bool terminal; struct Trie *son[sonnum]; }; Trie *NewTrie() { Trie *temp = new Trie; temp -> num = 1; temp -> terminal = false; for(int i = 0;i < sonnum;i++) temp -> son[i] = NULL; return temp; } void Insert(Trie *pnt,char *s,int len) { Trie *temp = pnt; for(int i = 0;i < len;i++) { if(temp -> son[s[i] - '0'] == NULL) temp -> son[s[i]-'0'] = NewTrie(); else { if(temp -> son[s[i]-'0'] -> terminal == true) { ok = 0; return; } temp -> son[s[i] - '0'] -> num++; } temp = temp -> son[s[i] - '0']; } temp -> terminal = true; if(temp -> num > 1) ok = 0; return; } void del(Trie *pnt) { for(int i = 0;i < sonnum;i++) { if(pnt -> son[i] != NULL) del(pnt -> son[i]); } free(pnt); }//释放内存的函数 int main() { int T,n; char a[10]; scanf("%d",&T); while(T--) { Trie *tree = NewTrie(); scanf("%d",&n); while(n--) { scanf("%s",a); if(ok) Insert(tree,a,strlen(a)); } if(ok == 1) puts("YES"); else if(ok == 0) puts("NO"); ok = 1; del(tree); } return 0; } //动态建树会t