• <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>

            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 閱讀(362) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm 、USACO

            導航

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

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            色婷婷综合久久久久中文字幕| 久久亚洲精品无码aⅴ大香| 国产精品久久久久无码av| 一本一道久久精品综合| 欧美午夜A∨大片久久| 亚洲精品无码久久千人斩| 久久线看观看精品香蕉国产| 久久久亚洲精品蜜桃臀| 欧美喷潮久久久XXXXx| 丁香久久婷婷国产午夜视频| 无码人妻久久一区二区三区蜜桃| 亚洲精品美女久久久久99| 国产视频久久| 国产精品一久久香蕉国产线看| 久久99精品久久久久久齐齐| 亚洲欧美伊人久久综合一区二区| 中文字幕亚洲综合久久2| 欧美大香线蕉线伊人久久| 亚洲欧洲精品成人久久奇米网| 91精品国产综合久久精品| 无码八A片人妻少妇久久| 久久精品夜色噜噜亚洲A∨| 99热成人精品热久久669| 久久伊人精品一区二区三区| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 9久久9久久精品| 色88久久久久高潮综合影院| 中文精品久久久久人妻| 久久久久久A亚洲欧洲AV冫| 久久免费精品视频| 久久91精品国产91久久小草| 亚洲人成精品久久久久| 中文字幕无码久久久| 理论片午午伦夜理片久久| 久久精品国产99久久丝袜| 亚洲国产成人久久综合一| 久久91精品国产91久久麻豆 | 国产精品久久久福利| 久久精品国产亚洲AV香蕉| 久久99国产综合精品女同| www久久久天天com|