今天學(xué)習(xí)了字典樹
做了一些以前用二分搜索解決的題目
hdoj的1075
http://acm.hdu.edu.cn/showproblem.php?pid=1075用很腦殘的方法過的，每個(gè)節(jié)點(diǎn)有設(shè)置11個(gè)字符(n)記錄，這樣浪費(fèi)空間很大
看過后臺(tái)數(shù)據(jù)，最大長(zhǎng)度是4，有26^4個(gè)（字典序aaaa到zzzz）如果再多一點(diǎn)，內(nèi)存就爆了
效率很低。。這道題目字典樹不如二分
hdoj的1247
http://acm.hdu.edu.cn/showproblem.php?pid=1247也用了不是很好的方法過掉，枚舉每個(gè)字符分成兩段，看是不是在字典樹內(nèi)
用n標(biāo)記是不是一個(gè)單詞
hdoj的1251
http://acm.hdu.edu.cn/showproblem.php?pid=1251這個(gè)就是最基礎(chǔ)的字典樹了，n來(lái)標(biāo)記這個(gè)前綴的次數(shù)
hdoj的1298
http://acm.hdu.edu.cn/showproblem.php?pid=1298這道就比前幾道難了，dfs所有數(shù)字變成字母的可能情況，然后找到最大的概率的打印
dfs借鑒了yifeifen的int hash[10][2]={0,0, 0,0, 0,2, 3,5, 6,8, 9,11, 12,14, 15,18, 19, 21, 22,25};來(lái)記錄每個(gè)數(shù)字對(duì)應(yīng)的字母
這個(gè)就方便多了。。。
我用了最差的效率過的，每次都重新找一邊，本來(lái)還超時(shí)的，后來(lái)優(yōu)化一下，已經(jīng)MANUALLY的就不用繼續(xù)找下去了，后來(lái)的保證都MANUALLY
了。。。
還有usaco的一道
1 Contact
2 IOI'98
3
4 The cows have developed a new interest in scanning the universe outside their farm with radiotelescopes. Recently, they noticed a very curious microwave pulsing emission sent right from the centre of the galaxy. They wish to know if the emission is transmitted by some extraterrestrial form of intelligent life or if it is nothing but the usual heartbeat of the stars.
5
6 Help the cows to find the Truth by providing a tool to analyze bit patterns in the files they record. They are seeking bit patterns of length A through B inclusive (1 <= A <= B <= 12) that repeat themselves most often in each day's data file. They are looking for the patterns that repeat themselves most often. An input limit tells how many of the most frequent patterns to output.
7
8 Pattern occurrences may overlap, and only patterns that occur at least once are taken into account.
9 PROGRAM NAME: contact
10 INPUT FORMAT
11 Line 1: Three space-separated integers: A, B, N; (1 <= N < 50)
12 Lines 2 and beyond: A sequence of as many as 200,000 characters, all 0 or 1; the characters are presented 80 per line, except potentially the last line.
13 SAMPLE INPUT (file contact.in)
14
15 2 4 10
16 01010010010001000111101100001010011001111000010010011110010000000
17
18
19 In this example, pattern 100 occurs 12 times, and pattern 1000 occurs 5 times. The most frequent pattern is 00, with 23 occurrences.
20 OUTPUT FORMAT
21
22 Lines that list the N highest frequencies (in descending order of frequency) along with the patterns that occur in those frequencies. Order those patterns by shortest-to-longest and increasing binary number for those of the same frequency. If fewer than N highest frequencies are available, print only those that are.
23
24 Print the frequency alone by itself on a line. Then print the actual patterns space separated, six to a line (unless fewer than six remain).
25 SAMPLE OUTPUT (file contact.out)
26
27 23
28 00
29 15
30 01 10
31 12
32 100
33 11
34 11 000 001
35 10
36 010
37 8
38 0100
39 7
40 0010 1001
41 6
42 111 0000
43 5
44 011 110 1000
45 4
46 0001 0011 1100
47
大意就是叫你找出
01010010010001000111101100001010011001111000010010011110010000000
長(zhǎng)度2于4之間的出現(xiàn)頻率最高10個(gè)串
是TTBJ大大介紹我做的。。
寫了一個(gè)半小時(shí)，終于把sample過掉了，叫TTBJ幫我提交，記過RE。。。。
他幫我檢查了一下說(shuō)別用指針，常常會(huì)出現(xiàn)錯(cuò)誤的。。。
給了我一個(gè)用數(shù)組的模板
可惜我試了下好像C語(yǔ)言無(wú)法使用，只能割愛了。。。
今天下午用TTBJ的模板再次嘗試好幾遍只后
終于AC了，好開心阿
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 struct tree{
5 char data;
6 int cnt,child[2];
7 void init(char c){
8 memset(child,0,sizeof(child));
9 data = c;
10 cnt = 0;
11 }
12 }T[1000001];
13 struct H{
14 int n;
15 char ch[13];
16 }hh[10000];
17 int L = 1;
18 int a,b,n,k,ans;
19 char ch[200001],temp[13];
20
21 void Ins(char *a,int k,int idx)
22 {
23 if(!a[k])
24 {
25 T[idx].cnt ++;
26 return ;
27 }
28 if(T[idx].child[ a[k]-'0' ])
29 Ins(a,k+1,T[idx].child[a[k]-'0']);
30 else
31 {
32 T[idx].child[a[k]-'0'] = ++L;
33 T[L].init(a[k]);
34 Ins(a,k+1,L);
35 }
36 }
37 void Creat()
38 {
39 int i,j,l,ii,len = strlen(ch);
40 char s[13];
41 for(i=0;ch[i];i++)
42 {
43 for(l=a,j=i,ii=0;l<=b;l++)
44 {
45 if(i+l>len)
46 break;
47 for(;j<i+l;j++,ii++)
48 {
49 s[ii] = ch[j];
50 }
51 s[ii] = 0;
52 Ins(s,0,1);
53 }
54 }
55 }
56 void find(char *a,int k,int idx)
57 {
58 if(!a[k])
59 {
60 ans = T[idx].cnt;
61 return ;
62 }
63 if(T[idx].child[a[k]-'0']==0)
64 return ;
65 find(a,k+1,T[idx].child[a[k]-'0']);
66 }
67
68 void dfs(int i)
69 {
70 if(i==b)
71 return ;
72 temp[i+1] = 0;
73
74 temp[i] = '0';
75 if(a<=i+1)
76 {
77 strcpy(hh[k].ch,temp);
78 ans = 0;
79 find(temp,0,1);
80 hh[k].n = ans;//符合條件，找
81 k++;
82 }
83 dfs(i+1);
84
85 temp[i+1] = 0;
86 temp[i] = '1';
87 if(a<=i+1)
88 {
89 strcpy(hh[k].ch,temp);
90 ans = 0;
91 find(temp,0,1);
92 hh[k].n = ans;
93 k++;
94 }
95 dfs(i+1);
96 }
97 int to_2(char *a,char *b)
98 {
99 int aa=0,bb=0;
100 for(;*a;a++)
101 aa = aa*2 + *a -'0';
102 for(;*b;b++)
103 bb = bb*2 + *b -'0';
104 return aa>bb?1:-1;
105 }
106 int cmp(const void *a,const void *b)
107 {
108 struct H * c = (struct H *)a;
109 struct H * d = (struct H *)b;
110 if(d->n == c->n)
111 {
112 if(strlen(c->ch) == strlen(d->ch))
113 return to_2(c->ch,d->ch);
114 return strlen(c->ch) - strlen(d->ch);
115 }
116 return d->n - c->n;
117 }
118 int main()
119 {
120 int i,count,sum,cnt;
121 while (scanf("%d%d%d",&a,&b,&n)==3)
122 {
123 if(a>b)
124 a^=b,b^=a,a^=b;
125 ch[0] = 0;
126 while(scanf("%s",temp)==1)
127 strcat(ch,temp);
128 Creat();//建樹
129 k = 0;
130 dfs(0);//枚舉所有點(diǎn)
131 qsort(hh,k,sizeof(hh[0]),cmp);
132 count = -1;
133 i = 0;
134 sum = -1;
135
136 while (1)//輸出
137 {
138 if(hh[i].n!=sum)
139 {
140 if(i)
141 puts("");
142 count ++;
143 if(count == n)
144 break;
145 sum = hh[i].n;
146 printf("%d\n",hh[i].n);
147 printf("%s",hh[i].ch);
148 i++;
149 if(hh[i].n==0)
150 {
151 puts("");
152 break;
153 }
154 cnt = 1;
155 }
156 else
157 {
158 cnt ++;
159 if(cnt == 7)
160 {
161 cnt = 1;
162 puts("");
163 }
164 else
165 printf(" ");
166 printf("%s",hh[i].ch);
167 i++;
168 if(hh[i].n==0)
169 {
170 puts("");
171 break;
172 }
173 }
174 }
175 }
176 return 0;
177 }
好吧，字典樹算是掌握了基礎(chǔ)，明天的任務(wù)：
線段樹~！
posted on 2009-02-10 02:11
shǎ崽 閱讀(531)
評(píng)論(0) 編輯 收藏 引用