国产精品你懂得,欧美性开放视频,最新精品在线

HDOJ 1671 Phone List

簡要分析字典樹問題。但是要釋放內存，否則會MLE.... = =!

代碼

1 #include <iostream>
2
3 bool flag=false;//重復標記
4 const int MAXSIZE=10;
5 struct Trie
6 {
7     int tail;//標記結束
8     int count;//標記頻率
9     Trie *next[MAXSIZE];
10     Trie()
11     {
12         tail=0;
13         count=1;
14         for (int i=0;i<MAXSIZE;i++)
15         {
16             next[i]=NULL;
17         }
18     }
19 };
20
21 //建樹擴展：當有結尾的點出現頻率大于1次表示有重復
22 void InsertWorldEx(Trie* &root,char *world)
23 {
24     Trie *location=root;
25     int i=0,branch=0,len;
26
27     len=strlen(world);
28     while (world[i])
29     {
30         branch=world[i]-'0';
31         if(location->next[branch]==NULL)
32              location->next[branch]=new Trie;
33         else
34         {
35             location->next[branch]->count++;
36         }
37
38         if(i==len-1)  location->next[branch]->tail=1;
39
40         //標記已經有前綴重復
41         if(location->next[branch]->tail==1&&location->next[branch]->count>1)
42             flag=true;
43
44         i++;
45         location=location->next[branch];
46     }
47 }
48 int del(Trie* &root)
49 {
50     int i;
51     if(root==NULL)
52         return 0;
53     for (i=0;i<MAXSIZE;i++)
54     {
55         if(root->next[i]!=NULL)
56             del(root->next[i]);
57     }
58     free(root);
59     return 0;
60 }
61
62 int main()
63 {
64     int t;
65     scanf("%d",&t);
66     while(t--)
67     {
68         int num;
69         char phone[20];
70         Trie *root=new Trie;
71         flag=false;
72
73         scanf("%d",&num);
74         for (int i=0;i<num;i++)
75         {
76             scanf("%s",phone);
77             if(flag==false) InsertWorldEx(root,phone);
78         }
79
80         if(flag) printf("NO\n");
81         else printf("YES\n");
82         del(root);
83     }
84     return 0;
85 }
86

相似題目HDOJ 1305 http://acm.hdu.edu.cn/showproblem.php?pid=1305

posted on 2010-10-05 22:51 Geek.tan 閱讀(343) 評論(0) 編輯收藏引用所屬分類: ACM解題報告

只有注冊用戶登錄后才能發表評論。


相關文章: HDOJ 1671 Phone List HDOJ 2539 點球大戰 --水題阿，但我就是錯了幾次 7月份HDOJ A題小結 HDOJ 1195 Open the Lock--BFS HDOJ 1003 MaxSum--最大子序列和 HDOJ 1789 Doing Homework again--經典貪心問題 HDOJ 1010 Tempter of the Bone--DFS+奇偶剪枝

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

單鏈DNA

HDOJ 1671 Phone List

導航

統計

公告

隨筆分類(40)

隨筆檔案(48)

搜索

積分與排名

最新評論

評論排行榜