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

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            婷婷久久香蕉五月综合加勒比| 狠狠88综合久久久久综合网| 午夜精品久久久久9999高清| 亚洲日韩欧美一区久久久久我| 国产成人精品三上悠亚久久| 99久久国产综合精品麻豆| 国产高潮久久免费观看| 久久人人青草97香蕉| 中文成人久久久久影院免费观看| 久久99九九国产免费看小说| 色综合久久综精品| 国内精品久久久久影院免费| 久久一区二区三区99| 久久棈精品久久久久久噜噜| 人妻无码精品久久亚瑟影视| 国产亚洲精品美女久久久| 伊人久久精品影院| 国内精品伊人久久久久影院对白| 久久精品国产精品亚洲毛片| 欧美久久久久久午夜精品| 国产成人精品久久亚洲高清不卡| 久久综合狠狠综合久久综合88| 亚洲欧美一级久久精品| 久久精品亚洲欧美日韩久久| 婷婷久久综合九色综合98| 久久综合狠狠综合久久综合88| 精品综合久久久久久98| 亚洲国产天堂久久综合| 国产精品久久久久久久久久免费| 精品久久久噜噜噜久久久| 无码人妻精品一区二区三区久久久| 久久99国产精品久久99小说| 亚洲国产高清精品线久久| 伊色综合久久之综合久久| 亚洲精品无码久久毛片| 一级做a爰片久久毛片毛片| 久久久久国色AV免费看图片 | 伊人久久大香线蕉精品不卡 | 91久久精品91久久性色| 亚洲av日韩精品久久久久久a| 亚洲AV日韩AV永久无码久久|