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

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            色婷婷久久久SWAG精品| 久久久久久亚洲Av无码精品专口| 国产精品久久自在自线观看| 伊人久久免费视频| 国产精品乱码久久久久久软件| 亚洲中文字幕无码久久2020| 久久国产精品-久久精品| 一本大道久久东京热无码AV| 少妇久久久久久久久久| 国产伊人久久| 97久久精品无码一区二区| 欧美伊人久久大香线蕉综合69| 久久水蜜桃亚洲av无码精品麻豆| 久久综合狠狠色综合伊人| 丁香色欲久久久久久综合网| 国产精品免费久久久久久久久| 久久久久久精品久久久久| 中文字幕一区二区三区久久网站| 精品熟女少妇AV免费久久 | 精品久久人妻av中文字幕| 国产精品欧美亚洲韩国日本久久 | 丁香五月网久久综合| 国内精品久久国产| 久久久久亚洲精品中文字幕| 久久国产精品久久精品国产| 国产亚洲精品自在久久| 欧美精品乱码99久久蜜桃| 免费一级做a爰片久久毛片潮| 伊人久久综在合线亚洲2019| 久久青草国产手机看片福利盒子| 国产精品无码久久综合| 久久精品国产亚洲AV嫖农村妇女| 久久久久久久精品妇女99| 久久天天躁狠狠躁夜夜avapp| 思思久久99热免费精品6| 久久一区二区三区99| 久久精品无码一区二区日韩AV| 亚洲国产精品一区二区久久| 中文字幕亚洲综合久久2| 久久精品无码一区二区三区日韩| 久久久WWW成人|