HDOJ1305解题报告【字典树】

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1305

题目概述：

　　给出几组编码，对于每组编码若存在编码i是编码j的前缀则输出not。

大致思路：

　　挺直白的tire树，不过我的做法并没有把所有编码插入树中，而是一边插入一边判断，出现not的情况之后所有编码都不需要进行处理了。

　　字符串类的题一定要注意输入处理！！！

　　重要的事情说三遍！！！

复杂度分析：略

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <vector>
 6 #include <ctime>
 7 #include <map>
 8 #include <queue>
 9 #include <cstring>
10 #include <algorithm>
11 using namespace std;
12 
13 #define sacnf scanf
14 #define maxn 5
15 #define inf 1061109567
16 #define Eps 0.001
17 #define PI 3.1415927
18 #define mod 9973
19 #define MAXNUM 10000
20 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
21 int Abs(int x) {return (x<0)?-x:x;}
22 typedef long long ll;
23 
24 struct node
25 {
26     bool End;
27     node *next[maxn];
28 } tire;
29 
30 bool Insert(node *root,char *s)
31 {
32     node *p=root;
33     while(*s!='')
34     {
35         if(p->next[*s-'0']==NULL)
36         {
37             node *temp=(node*)malloc(sizeof(node));
38             for(int i=0;i<maxn;i++) temp->next[i]=NULL;
39             p->next[*s-'0']=temp;p->End=temp->End=false;
40             p=p->next[*s-'0'];
41         }
42         else
43         {
44             p=p->next[*s-'0'];
45             if(p->End) return false;
46         }
47         s++;
48     }
49     return p->End=true;
50 }
51 
52 int main()
53 {
54     //freopen("data.in","r",stdin);
55     //freopen("data.out","w",stdout);
56     //clock_t st=clock();
57     char s[1010];int kase=1;
58     node *root=(node*)malloc(sizeof(node));root->End=false;
59     for(int i=0;i<maxn;i++) root->next[i]=NULL;
60     bool ans=true;
61     while(scanf("%s",s)!=EOF)
62     {
63         if(s[0]=='9')
64         {
65             root=(node*)malloc(sizeof(node));root->End=false;
66             for(int i=0;i<maxn;i++) root->next[i]=NULL;
67             if(ans) printf("Set %d is immediately decodable
",kase);
68             else printf("Set %d is not immediately decodable
",kase);
69             kase++;ans=true;continue;
70         }
71         if(!ans) continue;
72         if(!Insert(root,s)) ans=false;
73     }
74     //clock_t ed=clock();
75     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
76     return 0;
77 }