亚洲精品无码久久久久,青青草国产成人久久91网,亚洲午夜福利精品久久

換了個(gè)地址：http://www.cnblogs.com/vizhen/

HDOJ 1671 Phone List

簡(jiǎn)要分析字典樹(shù)問(wèn)題。但是要釋放內(nèi)存，否則會(huì)MLE.... = =!

代碼

1 #include <iostream>
2
3 bool flag=false;//重復(fù)標(biāo)記
4 const int MAXSIZE=10;
5 struct Trie
6 {
7     int tail;//標(biāo)記結(jié)束
8     int count;//標(biāo)記頻率
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 //建樹(shù)擴(kuò)展：當(dāng)有結(jié)尾的點(diǎn)出現(xiàn)頻率大于1次表示有重復(fù)
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         //標(biāo)記已經(jīng)有前綴重復(fù)
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 閱讀(327) 評(píng)論(0) 編輯收藏引用所屬分類: ACM解題報(bào)告

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: HDOJ 1671 Phone List HDOJ 2539 點(diǎn)球大戰(zhàn) --水題阿，但我就是錯(cuò)了幾次 7月份HDOJ A題小結(jié) HDOJ 1195 Open the Lock--BFS HDOJ 1003 MaxSum--最大子序列和 HDOJ 1789 Doing Homework again--經(jīng)典貪心問(wèn)題 HDOJ 1010 Tempter of the Bone--DFS+奇偶剪枝

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

單鏈DNA

HDOJ 1671 Phone List

導(dǎo)航

統(tǒng)計(jì)

公告

隨筆分類(40)

隨筆檔案(48)

搜索

積分與排名

最新評(píng)論

評(píng)論排行榜