• <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)  編輯 收藏 引用 所屬分類: AlgorithmUSACO

            導航

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

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            欧美精品久久久久久久自慰| 久久中文字幕一区二区| 中文成人无码精品久久久不卡| 伊人久久无码精品中文字幕| 久久精品国产2020| 91久久成人免费| 久久99国产综合精品免费| 成人午夜精品久久久久久久小说 | 亚洲中文字幕久久精品无码喷水 | 久久99精品国产麻豆不卡| 亚洲国产综合久久天堂 | 久久久久成人精品无码 | 久久强奷乱码老熟女网站| 久久亚洲国产成人精品性色| 麻豆国内精品久久久久久| 久久综合狠狠综合久久激情 | 99精品久久精品一区二区| 欧美日韩中文字幕久久伊人| 蜜臀久久99精品久久久久久小说| 久久国产成人| 青青草原综合久久| 久久久久久亚洲精品成人| 久久人人爽人人爽人人爽| 亚洲欧美国产精品专区久久| 国内精品久久久久久久coent| 2020久久精品国产免费| 久久久久女人精品毛片| 欧美大香线蕉线伊人久久| 日韩久久久久久中文人妻 | 久久人搡人人玩人妻精品首页| www.久久99| 四虎国产精品免费久久5151| 国产精品美女久久久久| 国产精品对白刺激久久久| 国产亚洲综合久久系列| 国产91久久精品一区二区| 国内精品久久久久影院免费| 久久免费高清视频| 国产精品成人无码久久久久久| 狠狠人妻久久久久久综合蜜桃| 久久久久久久亚洲精品|