• <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>
            隨筆-72  評論-126  文章-0  trackbacks-0
            今天學習了字典樹
            做了一些以前用二分搜索解決的題目
            hdoj的1075
            http://acm.hdu.edu.cn/showproblem.php?pid=1075
            用很腦殘的方法過的,每個節點有設置11個字符(n)記錄,這樣浪費空間很大
            看過后臺數據,最大長度是4,有26^4個(字典序aaaa到zzzz)如果再多一點,內存就爆了
            效率很低。。這道題目字典樹不如二分

            hdoj的1247
            http://acm.hdu.edu.cn/showproblem.php?pid=1247
            也用了不是很好的方法過掉,枚舉每個字符分成兩段,看是不是在字典樹內
            用n標記是不是一個單詞

            hdoj的1251
            http://acm.hdu.edu.cn/showproblem.php?pid=1251
            這個就是最基礎的字典樹了,n來標記這個前綴的次數

            hdoj的1298
            http://acm.hdu.edu.cn/showproblem.php?pid=1298
            這道就比前幾道難了,dfs所有數字變成字母的可能情況,然后找到最大的概率的打印
            dfs借鑒了yifeifen的int hash[10][2]={0,0, 0,0, 0,2, 3,5, 6,8, 9,11, 12,14, 15,18, 19, 21, 22,25};來記錄每個數字對應的字母
            這個就方便多了。。。
            我用了最差的效率過的,每次都重新找一邊,本來還超時的,后來優化一下,已經MANUALLY的就不用繼續找下去了,后來的保證都MANUALLY
            了。。。

            還有usaco的一道
             1 Contact
             2 IOI'98
             3 
             4 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.
             5 
             6 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.
             7 
             8 Pattern occurrences may overlap, and only patterns that occur at least once are taken into account.
             9 PROGRAM NAME: contact
            10 INPUT FORMAT
            11 Line 1:     Three space-separated integers: A, B, N; (1 <= N < 50)
            12 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.
            13 SAMPLE INPUT (file contact.in)
            14 
            15 2 4 10
            16 01010010010001000111101100001010011001111000010010011110010000000
            17 
            18 
            19 In this example, pattern 100 occurs 12 times, and pattern 1000 occurs 5 times. The most frequent pattern is 00, with 23 occurrences.
            20 OUTPUT FORMAT
            21 
            22 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.
            23 
            24 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).
            25 SAMPLE OUTPUT (file contact.out)
            26 
            27 23
            28 00
            29 15
            30 01 10
            31 12
            32 100
            33 11
            34 11 000 001
            35 10
            36 010
            37 8
            38 0100
            39 7
            40 0010 1001
            41 6
            42 111 0000
            43 5
            44 011 110 1000
            45 4
            46 0001 0011 1100
            47 


            大意就是叫你找出
            01010010010001000111101100001010011001111000010010011110010000000
            長度2于4之間的出現頻率最高10個串

            是TTBJ大大介紹我做的。。
            寫了一個半小時,終于把sample過掉了,叫TTBJ幫我提交,記過RE。。。。
            他幫我檢查了一下說別用指針,常常會出現錯誤的。。。
            給了我一個用數組的模板
            可惜我試了下好像C語言無法使用,只能割愛了。。。

            今天下午用TTBJ的模板再次嘗試好幾遍只后
            終于AC了,好開心阿
              1 #include<stdio.h>
              2 #include<string.h>
              3 #include<stdlib.h>
              4 struct tree{
              5     char data;
              6     int cnt,child[2];
              7     void init(char c){
              8         memset(child,0,sizeof(child));
              9         data = c;
             10         cnt = 0;
             11     }
             12 }T[1000001];
             13 struct H{
             14     int n;
             15     char ch[13];
             16 }hh[10000];
             17 int L = 1;
             18 int a,b,n,k,ans;
             19 char ch[200001],temp[13];
             20 
             21 void Ins(char *a,int k,int idx)
             22 {
             23     if(!a[k])
             24     {
             25         T[idx].cnt ++;
             26         return ;
             27     }
             28     if(T[idx].child[ a[k]-'0' ])
             29         Ins(a,k+1,T[idx].child[a[k]-'0']);
             30     else
             31     {
             32         T[idx].child[a[k]-'0'= ++L;
             33         T[L].init(a[k]);
             34         Ins(a,k+1,L);
             35     }
             36 }
             37 void Creat()
             38 {
             39     int i,j,l,ii,len = strlen(ch);
             40     char s[13];
             41     for(i=0;ch[i];i++)
             42     {
             43         for(l=a,j=i,ii=0;l<=b;l++)
             44         {
             45             if(i+l>len)
             46                 break;
             47             for(;j<i+l;j++,ii++)
             48             {
             49                 s[ii] = ch[j];
             50             }
             51             s[ii] = 0;
             52             Ins(s,0,1);
             53         }
             54     }
             55 }
             56 void find(char *a,int k,int idx)
             57 {
             58     if(!a[k])
             59     {
             60         ans = T[idx].cnt;
             61         return ;
             62     }
             63     if(T[idx].child[a[k]-'0']==0)
             64         return ;
             65     find(a,k+1,T[idx].child[a[k]-'0']);
             66 }
             67 
             68 void dfs(int i)
             69 {
             70     if(i==b)
             71         return ;
             72     temp[i+1= 0
             73 
             74     temp[i] = '0';
             75     if(a<=i+1)
             76     {
             77         strcpy(hh[k].ch,temp);
             78         ans = 0;
             79         find(temp,0,1);
             80         hh[k].n = ans;//符合條件,找
             81         k++;
             82     }
             83     dfs(i+1);
             84     
             85     temp[i+1= 0
             86     temp[i] = '1';
             87     if(a<=i+1)
             88     {
             89         strcpy(hh[k].ch,temp);
             90         ans = 0;
             91         find(temp,0,1);
             92         hh[k].n = ans;
             93         k++;
             94     }
             95     dfs(i+1);
             96 }
             97 int to_2(char *a,char *b)
             98 {
             99     int aa=0,bb=0;
            100     for(;*a;a++)
            101         aa = aa*2 + *-'0';
            102     for(;*b;b++)
            103         bb = bb*2 + *-'0';
            104     return aa>bb?1:-1;
            105 }
            106 int cmp(const void *a,const void *b)
            107 {
            108     struct H * c = (struct H *)a;
            109     struct H * d = (struct H *)b;
            110     if(d->== c->n)
            111     {
            112         if(strlen(c->ch) == strlen(d->ch))
            113             return to_2(c->ch,d->ch);
            114         return strlen(c->ch) - strlen(d->ch);
            115     }
            116     return d->- c->n;
            117 }
            118 int main()
            119 {
            120     int i,count,sum,cnt;
            121     while (scanf("%d%d%d",&a,&b,&n)==3)
            122     {
            123         if(a>b)
            124             a^=b,b^=a,a^=b;
            125         ch[0= 0;
            126         while(scanf("%s",temp)==1)
            127             strcat(ch,temp);
            128         Creat();//建樹
            129         k = 0;
            130         dfs(0);//枚舉所有點
            131         qsort(hh,k,sizeof(hh[0]),cmp);
            132         count = -1;
            133         i = 0;
            134         sum = -1;
            135         
            136         while (1)//輸出
            137         {
            138             if(hh[i].n!=sum)
            139             {
            140                 if(i)
            141                     puts("");
            142                 count ++;
            143                 if(count == n)
            144                     break;
            145                 sum = hh[i].n;
            146                 printf("%d\n",hh[i].n);
            147                 printf("%s",hh[i].ch);
            148                 i++;
            149                 if(hh[i].n==0)
            150                 {
            151                     puts("");
            152                     break;
            153                 }
            154                 cnt = 1;
            155             }
            156             else
            157             {
            158                 cnt ++;
            159                 if(cnt == 7)
            160                 {
            161                     cnt = 1;
            162                     puts("");
            163                 }
            164                 else 
            165                     printf(" ");
            166                 printf("%s",hh[i].ch);
            167                 i++;
            168                 if(hh[i].n==0)
            169                 {
            170                     puts("");
            171                     break;
            172                 }
            173             }
            174         }
            175     }
            176     return 0;
            177 }



            好吧,字典樹算是掌握了基礎,明天的任務:線段樹~!
            posted on 2009-02-10 02:11 shǎ崽 閱讀(520) 評論(0)  編輯 收藏 引用
            久久久久久久久久久| 久久精品无码专区免费东京热| 久久久久免费精品国产| 91精品国产色综合久久| 亚洲国产精久久久久久久| 久久综合狠狠综合久久97色| 久久久久久久精品妇女99| 丰满少妇人妻久久久久久 | 日本精品一区二区久久久| 日韩亚洲国产综合久久久| 亚洲成色www久久网站夜月| 久久久久久久综合日本亚洲 | 一本色综合网久久| 狠色狠色狠狠色综合久久| 一本久久免费视频| 久久精品一区二区| 一级女性全黄久久生活片免费| 久久av无码专区亚洲av桃花岛| 久久青青国产| 久久96国产精品久久久| 亚洲国产香蕉人人爽成AV片久久| 久久精品国产亚洲AV麻豆网站| 青青热久久国产久精品| 久久99国产精品久久久| 久久频这里精品99香蕉久| 久久久久夜夜夜精品国产| 色欲av伊人久久大香线蕉影院 | 日日躁夜夜躁狠狠久久AV| 久久99精品久久久久久不卡| 久久精品人人做人人妻人人玩| 亚洲精品99久久久久中文字幕 | 久久精品国产亚洲AV久| 久久久久这里只有精品| 国产精品狼人久久久久影院| 精品久久香蕉国产线看观看亚洲| 亚洲愉拍99热成人精品热久久| 亚洲精品无码久久久| 99久久夜色精品国产网站| 久久久久夜夜夜精品国产| 97超级碰碰碰久久久久| 潮喷大喷水系列无码久久精品|