学步园

http://acm.pku.edu.cn/JudgeOnline/problem?id=1174

题目要求给丁一个01字符串，并且给丁A，B，N要求找出长度A<=Len<=B 的出现频率最高的N中字符串。

如果出现频率相同按照字符串长度排序，如果长度也相同，按照字典序排序。我用类似tire 树的方法解这到

题目，当然速度比较慢。1032ms -.-b 。由于串只有01，那么我们可以建立如下的树：

这个类似字典树的树，由于只有两个儿子，那么可以用类似堆的结构来保存，我们对字符串进行插入操作，就像对字典树进行插入操作一样，统计次数，最后进行排序输出即可：

#include "iostream"<br /> #include "cstdio"<br /> #include "algorithm"<br /> using namespace std;<br /> const int MaxLen = 2010000;<br /> char str[MaxLen];<br /> int N,A,B,Len,cnt;<br /> int Arr[100000];<br /> typedef struct re{<br /> int num,len,time;<br /> }re;<br /> bool operator <(const re& a,const re& b){<br /> if(a.time > b.time) return true;<br /> if(a.time == b.time){<br /> if(a.len > b.len) return true;<br /> else if(a.len == b.len){<br /> if(a.num > b.num) return true;<br /> else return false;<br /> }else return false;<br /> }else return false;<br /> }<br /> re R[100000];<br /> int input(){<br /> scanf("%d%d",&A,&B);<br /> scanf("%d",&N);<br /> getchar();<br /> char tmp;<br /> int i = 0 ;<br /> while(tmp = getchar()){<br /> if(tmp == '2') break;<br /> else str[i++] = tmp;<br /> }<br /> return i;<br /> }<br /> int Insert(char* s,int len){<br /> int i = 1;<br /> for(int j = 0 ;j < len; ++j){<br /> if(s[j] == '0')<br /> i <<=1;<br /> else i = (i << 1) + 1;<br /> }<br /> ++Arr[i];<br /> }<br /> void work(){<br /> for(int i = A; i <= B; ++i)<br /> for(int j = 0 ;j <= Len - i; ++j)<br /> Insert(str + j,i);<br /> }<br /> void print(int num,int len){<br /> char tmp[20];<br /> int t = 0;<br /> while(t < len){<br /> if(num & 1) tmp[len - t-1] = '1';<br /> else tmp[len - t -1] = '0';<br /> ++t;<br /> num >>=1;<br /> }<br /> for(int i = 0 ;i <len; ++i)<br /> putchar(tmp[i]);<br /> putchar(' ');<br /> }<br /> void calc(){<br /> int down = (1 << A);<br /> int up = (1 << ( B + 1));<br /> for(int len = A; len <= B; ++len){<br /> for(int i = (1 << len);i < (1<<(len+1)); ++i){<br /> if(Arr[i] != 0){<br /> R[cnt].num = i; R[cnt].len = len; R[cnt].time = Arr[i];<br /> ++cnt;<br /> }<br /> }<br /> }<br /> }<br /> int main(){<br /> Len = input();<br /> work();<br /> calc();<br /> sort(R,R+cnt);<br /> int ccc = 0 ;<br /> int i = 0;<br /> while(i < cnt && ccc < N){<br /> int ttt = R[i].time;<br /> printf("%d ",R[i].time);<br /> while(R[i].time == ttt){<br /> print(R[i].num,R[i].len);<br /> ++i;<br /> }<br /> putchar('/n');<br /> ++ccc;<br /> }<br /> return 0;<br /> }<br />