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

USACO 3.1 Contact


字符串的長度有限(最多只有12位),我建一個trie樹來存儲所有字符串,然后遍歷trie樹,將對應的字符串存儲到一個vector中,再排序輸出。
ac以后,看usaco的分析,是用位串來做索引計數,這種方法比較簡潔巧妙。為了解決前綴為0的問題,在每個字符串前面加了一個1,輸出的時候再去掉。
我的解法如下:

#include?<iostream>
#include?
<fstream>
#include?
<vector>
#include?
<string>

using?namespace?std;

ifstream?fin(
"contact.in");
ofstream?fout(
"contact.out");

#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif

struct?trie_node{
????
int?cnt;
????trie_node
*?sons[2];
????trie_node(){
????????sons[
0]?=?sons[1]?=?0;
????????cnt?
=?0;
????}
};

struct?sort_node{
????
string?str;
????
int?cnt;

????
bool?operator<(const?sort_node&n2)?const{
????????
if(cnt!=n2.cnt)?return?cnt>n2.cnt;
????????
if(str.size()!=n2.str.size())?return?str.size()<n2.str.size();
????????
for(int?i=0;i<str.size();++i){
????????????
if(str[i]!=n2.str[i])
????????????????
return?str[i]<n2.str[i];
????????}
????}
};

char?buf[200000];
int?buf_len;
int?a,b,n;
vector
<sort_node>res;

void?insert_trie(trie_node*root,const?char?*start,int?len)
{
????trie_node?
*?next?=?root;

????
for(int?i=0;i<len;++i){
????????
if(next->sons[start[i]-'0']==NULL)
????????????next
->sons[start[i]-'0']?=?new?trie_node;
????????next?
=?next->sons[start[i]-'0'];
????????
if(i+1>=a&&i+1<=b)
????????????next
->cnt++;
????}
}

void?_traverse_trie(trie_node?*root,char?ch,int?depth)
{
????
if(root==NULL)?return;

????buf[depth]
=ch;

????
if(root->cnt!=0){
????????sort_node?n;
????????n.str?
=?string(&buf[0],&buf[depth+1]);
????????n.cnt?
=?root->cnt;
????????res.push_back(n);
????}

????_traverse_trie(root
->sons[0],'0',depth+1);
????_traverse_trie(root
->sons[1],'1',depth+1);
}

void?traverse_trie(trie_node?*root)
{
????_traverse_trie(root
->sons[0],'0',0);
????_traverse_trie(root
->sons[1],'1',0);
}


void?solve()
{
????
in>>a>>b>>n;

????
char?ch;
????
while(in.get(ch)){
????????
if(ch=='0'||ch=='1')
????????????buf[buf_len
++]?=?ch;
????}

????trie_node?root;

????
for(int?i=0;i+b<=buf_len;++i){
????????insert_trie(
&root,&buf[i],b);
????}

????
for(int?i=min(b-1,buf_len);i>=a;--i){
????????insert_trie(
&root,&buf[buf_len-i],i);
????}

????traverse_trie(
&root);

????sort(res.begin(),res.end());

????
int?freq_cnt?=?0;
????
int?last_cnt?=?-1;
????
int?out_cnt?=?0;

????
for(int?i=0;i<res.size();++i){
????????
if(res[i].cnt==last_cnt){
????????????
if(out_cnt%6!=0)
????????????
out<<"?";
????????????
out<<res[i].str;
????????????out_cnt
++;
????????????
if(out_cnt%6==0||i==(res.size()-1)||res[i+1].cnt!=res[i].cnt)
????????????????
out<<endl;
????????}
else{
????????????last_cnt?
=?res[i].cnt;
????????????freq_cnt
++;
????????????
if(freq_cnt>n)
???????????????
break;?
????????????
out<<res[i].cnt<<endl;
????????????
out<<res[i].str;
????????????out_cnt?
=?0;
????????????out_cnt
++;
????????????
if(?(i==res.size()-1)||res[i+1].cnt!=res[i].cnt)
????????????????
out<<endl;
????????}
????}
}

int?main(int?argc,char?*argv[])
{
????solve();?
????
return?0;
}


附題:
Contact
IOI'98

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.

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.

Pattern occurrences may overlap, and only patterns that occur at least once are taken into account.

PROGRAM NAME: contact

INPUT FORMAT

Line 1: Three space-separated integers: A, B, N; (1 <= N < 50)
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.

SAMPLE INPUT (file contact.in)

2 4 10
01010010010001000111101100001010011001111000010010011110010000000

In this example, pattern 100 occurs 12 times, and pattern 1000 occurs 5 times. The most frequent pattern is 00, with 23 occurrences.

OUTPUT FORMAT

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.

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).

SAMPLE OUTPUT (file contact.out)

23
00
15
01 10
12
100
11
11 000 001
10
010
8
0100
7
0010 1001
6
111 0000
5
011 110 1000
4
0001 0011 1100

posted on 2009-07-02 22:07 YZY 閱讀(370) 評論(0)  編輯 收藏 引用 所屬分類: AlgorithmUSACO

導航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

統計

常用鏈接

留言簿(2)

隨筆分類

隨筆檔案

搜索

積分與排名

最新評論

閱讀排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美一区二区三区在线| 亚洲精品自在久久| 亚洲欧美日韩国产| 日韩一级片网址| 国产精品久久久久久户外露出| 一本久久综合亚洲鲁鲁| 日韩视频免费观看高清在线视频| 欧美美女喷水视频| 亚洲午夜日本在线观看| 亚洲一区二区久久| 国产综合婷婷| 亚洲国产你懂的| 欧美日韩成人在线观看| 亚洲欧美日韩精品| 午夜精品剧场| 亚洲激情网站| 亚洲视频免费| 曰韩精品一区二区| 亚洲精品一区二区三区婷婷月| 欧美色欧美亚洲另类七区| 欧美一区二区三区视频免费播放| 亚洲欧美春色| 日韩一级视频免费观看在线| 亚洲视频在线观看| 亚洲高清色综合| 亚洲一区二区三区免费在线观看| 国产一区二区三区丝袜| 亚洲精品日韩在线观看| 国产日韩欧美日韩| 日韩一级欧洲| 91久久中文字幕| 翔田千里一区二区| 一本久久a久久免费精品不卡| 欧美亚洲视频在线观看| 亚洲精品影视在线观看| 欧美在线观看视频一区二区三区| 亚洲精品一二三区| 久久av二区| 亚洲欧美激情视频| 欧美国产三级| 欧美成人午夜| 国产亚洲欧美一区| 这里只有视频精品| 亚洲精品影院在线观看| 久久手机精品视频| 久久精品日产第一区二区| 欧美日韩国产一区二区三区| 免费亚洲一区二区| 国产一区二区三区久久| 亚洲一区二区三区免费在线观看| 夜夜嗨av一区二区三区中文字幕 | 久久亚洲欧洲| 欧美一区日韩一区| 国产精品国产三级国产a| 亚洲高清视频在线| 1000部国产精品成人观看| 午夜一级在线看亚洲| 亚洲欧美日韩精品综合在线观看| 欧美激情一区二区三区蜜桃视频| 欧美成人精精品一区二区频| 国产自产v一区二区三区c| 亚洲女性裸体视频| 欧美一区二区| 国产亚洲观看| 久久精品国产清自在天天线 | 亚洲电影免费在线观看| 久久影院亚洲| 欧美jizzhd精品欧美巨大免费| 含羞草久久爱69一区| 久久久久国色av免费观看性色| 欧美自拍偷拍| 国产在线不卡视频| 久久九九国产精品怡红院| 乱中年女人伦av一区二区| 在线观看欧美一区| 欧美极品一区二区三区| 日韩视频一区二区三区在线播放| 亚洲午夜久久久久久尤物| 国产精品成人在线| 久久福利毛片| 亚洲高清二区| 亚洲免费小视频| 国产精品自拍在线| 欧美一区免费| 亚洲福利免费| 亚洲无玛一区| 国产午夜精品视频免费不卡69堂| 欧美专区在线| 亚洲国产成人午夜在线一区| 一区二区三区免费网站| 国产美女精品人人做人人爽| 欧美一二区视频| 亚洲国产清纯| 欧美一二三区在线观看| 在线看片第一页欧美| 欧美日韩国产精品一区| 亚洲欧美制服另类日韩| 嫩模写真一区二区三区三州| 一区二区激情小说| 国语精品中文字幕| 欧美日韩视频一区二区三区| 欧美在线免费视屏| 亚洲精品乱码久久久久久蜜桃91| 亚洲一区美女视频在线观看免费| 国产一区二区三区的电影 | 91久久精品国产| 久久精品在线观看| 一区二区三区视频观看| 韩国精品一区二区三区| 欧美日韩激情网| 久久精品亚洲一区| 在线视频中文亚洲| 欧美黑人在线观看| 久久久999| 亚洲欧美久久久| 91久久精品国产91久久性色| 国产区日韩欧美| 欧美午夜免费电影| 欧美ed2k| 久久免费偷拍视频| 亚洲欧美激情诱惑| 99国产精品国产精品毛片| 男人的天堂亚洲| 久久久久在线观看| 欧美有码在线观看视频| 一区二区三区国产精品| 亚洲人成亚洲人成在线观看图片 | 国产欧美日韩一区二区三区在线| 欧美精品一区二区三区久久久竹菊| 久久国产精品毛片| 亚洲欧美电影在线观看| 一区二区福利| 99亚洲视频| 一区二区国产在线观看| 亚洲精品日韩欧美| 99日韩精品| 99视频超级精品| 亚洲美女电影在线| 99国产精品自拍| 日韩视频一区二区| 一本色道久久综合亚洲精品不| 亚洲国产婷婷香蕉久久久久久99 | 亚洲一区二区三区四区五区午夜| 亚洲人成在线观看一区二区 | 香蕉av777xxx色综合一区| 亚洲欧美欧美一区二区三区| 亚洲视频二区| 亚洲一区二区在线观看视频| 亚洲一区二区在线视频| 亚洲午夜激情网页| 午夜精品一区二区三区在线| 午夜一区二区三区不卡视频| 欧美一级视频精品观看| 久久动漫亚洲| 六月丁香综合| 亚洲欧洲视频在线| 一区二区高清视频| 午夜久久黄色| 久久婷婷久久| 欧美日韩成人精品| 国产精品免费一区豆花| 国产最新精品精品你懂的| 在线观看一区二区视频| 亚洲日产国产精品| 亚洲综合国产| 久久久久久综合网天天| 亚洲高清毛片| 中国女人久久久| 久久精品免费电影| 午夜综合激情| 亚洲欧洲精品一区二区精品久久久| 亚洲激情女人| 亚洲视频在线二区| 久久激情一区| 日韩视频在线观看| 性做久久久久久久久| 久热精品在线视频| 日韩亚洲欧美中文三级| 欧美一区午夜视频在线观看| 免费成人你懂的| 国产精品久久久久一区二区三区共| 国产一区欧美日韩| 99在线精品视频| 久久久久久久综合日本| 亚洲激情第一区| 午夜一区二区三视频在线观看| 欧美成人精品不卡视频在线观看| 国产精品久久久久久久久免费桃花 | 欧美成人午夜免费视在线看片| 国产精品国产精品国产专区不蜜| 亚洲东热激情| 欧美亚洲自偷自偷| 亚洲理论在线| 老鸭窝亚洲一区二区三区| 国产精品一二三| 夜久久久久久| 亚洲国产精品成人精品| 久久成人一区二区| 国产精品一区二区你懂的| 妖精成人www高清在线观看|