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

            bon

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(2)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            poj 3340
            給定兩個字符串:s跟t,長度一樣,均不超過10,但t只包含數字,而s除了數字還可能含有"?",問將問號變成數字后得到的數字中,有多少個數是大于t的。
            很明顯用搜索找出所有符合要求的數字即可。
            搜索從s的第一個字符s[0]開始,每次向下遞歸都檢查s的下一個字符s[level]。根據當前字符有一下幾種搜索方向:

            1. s[level]=='?', 設當前值為now,則下一個值可以是now*10+i, 0<=i<=9,只要這個值大于等于t[0~level]所表示的數字,則進入下一層遞歸:
                 dfs(now*10+i, level+1)。
            2. s[level]是一個數字要分兩種情況討論:若now*10+s[level]-'0'>=t[0~level]表示的數字,則dfs(now*10+s[level]-'0', level+1);否則就返回0,表示s跟t從0
                  到level這一段不符合要求。

            搜索的時候要注意優化,否則當s=“????????", t="00000000"時就要算很久。優化是當now*10+i > t[0~level]時,則j>i的情況都不用再遞歸計算了,因為dfs( now*10+{i+1 ,..., 9}, level+1)的結果跟dfs(now*10+i, level+1)的結果是一樣的。只要乘上9-i就可以了。

             1 #include <iostream>
             2 
             3 using namespace std;
             4 
             5 char s[11],t[11];
             6 int tt[11];
             7 int fact[11];
             8 int cnt;
             9 int len;
            10 
            11 __int64 dfs(int now,int level)
            12 {
            13     if(level==len){
            14         if(now>tt[level-1]) return 1;//cnt+=(now%fact[level-1]-tt[level-1]%fact[level-1]);
            15         return 0;
            16     }
            17     // 用0~9十個數字來代替?
            18     if(s[level]=='?'){
            19         int i=0;
            20         while(i<10 && now*10+i<tt[level]) i++;
            21         __int64 tmp=dfs(now*10+i,level+1);
            22         if(i+1<10) tmp+=(9-i)*dfs(now*10+i+1,level+1);
            23         return tmp;
            24     }else if(now*10+s[level]-'0'>=tt[level]){
            25         return dfs(now*10+s[level]-'0',level+1);
            26     }else{
            27         return 0;
            28     }
            29 }
            30 
            31 void solve()
            32 {
            33     int i,j,k;
            34     len=strlen(s);
            35     tt[0]=t[0]-'0';
            36     for(i=1;i<len;i++) tt[i]=tt[i-1]*10+t[i]-'0';
            37     cnt=0;
            38     printf("%I64d\n",dfs(0,0));
            39 }
            40 
            41 int main()
            42 {
            43     fact[0]=1;
            44     for(int i=1;i<=10;i++) fact[i]=fact[i-1]*10;
            45     while(true){
            46         scanf("%s",s);
            47         if(s[0]=='#'return 1;
            48         scanf("%s",t);
            49         solve();
            50     }
            51 }
            52 
            posted on 2008-05-12 00:59 bon 閱讀(415) 評論(1)  編輯 收藏 引用 所屬分類: Programming Contest

            Feedback

            # re: poj 3340 2009-02-18 16:07 czcomt
            不用DFS的,直接有數學規律的,找出滿足條件的最小的數就可以了  回復  更多評論
              

            Google PageRank 
Checker - Page Rank Calculator
            精品久久久无码人妻中文字幕 | 77777亚洲午夜久久多喷| 日本久久中文字幕| 午夜福利91久久福利| 伊人久久大香线蕉av一区| 国产综合久久久久| 久久久久亚洲AV综合波多野结衣| 少妇久久久久久被弄到高潮| 久久久久女人精品毛片| 日韩欧美亚洲综合久久影院Ds| 日韩人妻无码一区二区三区久久99| 久久精品国产亚洲AV嫖农村妇女| 91亚洲国产成人久久精品| 精品久久久久久中文字幕大豆网| 国产精品久久久久影院嫩草| 国产精品久久久久久久人人看 | 久久久久久久人妻无码中文字幕爆 | 无码人妻精品一区二区三区久久| 久久香蕉综合色一综合色88| 久久人人爽人人爽人人片av麻烦| 亚洲国产精品久久久久| 色综合久久久久无码专区| 久久亚洲中文字幕精品一区| 久久91综合国产91久久精品| 久久国产色av免费看| 思思久久好好热精品国产| 国产午夜精品久久久久九九| 国产精品久久永久免费| 亚洲AV成人无码久久精品老人 | 久久精品中文无码资源站| 久久久这里有精品中文字幕| 久久久无码精品午夜| 青青热久久国产久精品 | 伊人久久综合无码成人网| 亚洲国产精品无码久久九九| 欧美日韩中文字幕久久久不卡| 精品国产青草久久久久福利| 久久综合视频网站| 一本大道久久东京热无码AV| 久久精品国产男包| 精品久久久久久无码专区|