• <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 閱讀(363) 評論(0)  編輯 收藏 引用 所屬分類: AlgorithmUSACO

            導航

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

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            日本国产精品久久| 免费久久人人爽人人爽av| 精品久久久噜噜噜久久久| 日本久久久久亚洲中字幕| 国产情侣久久久久aⅴ免费| 国产2021久久精品| 一本一本久久a久久精品综合麻豆| 人人妻久久人人澡人人爽人人精品| 亚洲午夜久久久久久久久久 | 无码人妻精品一区二区三区久久| 久久久久亚洲AV无码网站| 久久久WWW成人| 996久久国产精品线观看| 久久综合狠狠综合久久 | 欧美精品丝袜久久久中文字幕 | 婷婷综合久久中文字幕| 久久伊人影视| 91精品国产91久久久久久蜜臀| 久久午夜福利无码1000合集| 99久久www免费人成精品| 亚洲AV日韩精品久久久久| 久久亚洲国产成人影院网站| 久久精品视频免费| 久久精品亚洲一区二区三区浴池 | 91久久成人免费| 亚洲AV日韩精品久久久久| 亚洲精品国产综合久久一线| 亚洲成人精品久久| 免费观看久久精彩视频| 精品久久久久久中文字幕人妻最新| 久久亚洲熟女cc98cm| 久久久久亚洲精品男人的天堂| 一级做a爱片久久毛片| 欧美精品一区二区精品久久| 久久永久免费人妻精品下载| 国产aⅴ激情无码久久| 97精品伊人久久大香线蕉| 中文字幕无码久久精品青草| 亚洲人成无码久久电影网站| 要久久爱在线免费观看| 伊人色综合九久久天天蜜桃|