随笔-65  评论-6  文章-0  trackbacks-0
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <malloc.h>
 5 struct Tries{
 6     bool exist;
 7     bool end;
 8     Tries *num[10];
 9     Tries(){
10         for(int i=0;i<10;i++)
11             num[i]=NULL;
12         exist=end=false;
13     }
14 };
15 
16 void insert(char *a,Tries *root){
17     Tries *temp=root;
18     int len=strlen(a);
19     int i;
20     for(i=0;i<len;i++){
21         int k=a[i]-'0';
22         if(temp->num[k]==NULL)
23             temp->num[k]=new Tries;
24         temp->exist=true;
25         temp=temp->num[k];
26     }
27     temp->end=true;
28 }
29 
30 bool find(char *a,Tries *root){
31     Tries *temp=root;
32     int len=strlen(a);
33     int i;
34     for(i=0;i<len;i++){
35         int k=a[i]-'0';
36         if(temp->end)
37             return true;
38         temp=temp->num[k];
39     }
40     if(temp->exist)
41         return true;
42     return false;
43 }
44 
45 void del(Tries *root){
46     int i;
47     for(i=0;i<10;i++)
48         if(root->num[i]!=NULL)
49             del(root->num[i]);
50     free(root);
51 }
52 int main(){
53     //freopen("in.txt","r",stdin);
54     int n;
55     scanf("%d",&n);
56     while (n--){
57         Tries *tree;
58         tree=new Tries;
59         bool getIt=false;
60         char str[11];
61         int t;
62         scanf("%d",&t);
63         getchar();
64         while (t--){
65             gets(str);
66             if(!getIt){
67                 insert(str,tree);
68                 getIt=find(str,tree);
69             }
70         }
71         if(getIt)
72             puts("NO");
73         else
74             puts("YES");
75         del(tree);
76 
77     }
78     return 0;
79 }
80 
posted on 2012-05-15 08:57 Leo.W 阅读(60) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理