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

            Why so serious? --[NKU]schindlerlee

            2009年11月22日星期日.sgu154 sgu175

            2009年11月22日星期日.sgu154 sgu175

            sgu154:非常好的數論+二分題目
            You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 1*2*...*N. For example, 5! = 120, 120 contains one zero on the trail.

            Input
            One number Q written in the input (0<=Q<=10^8).

            Output
            Write "No solution", if there is no such number N, and N otherwise.

            Sample test(s)
            Input
            2
            Output
            10

            首先要明白一件事x!末尾的0的個數至于2和5的個數有關,又因為2的個數已經多余5,所以階乘末尾
            0的個數完全等價于所有數中5的個數
            所以階乘末尾0的個數可以用如下函數計算
            int count(int x) //count the num of 0s in x!
            {
                int res = 0;
                while(x > 0) {
                    res += x / 5;
                    x /= 5;
                }
                return res;
            }
            然后題目要求末尾個數有n個0的x!中,x為多少
            因為哦count函數具有單調增加的性質,所以完全可以二分尋找符合條件的x
            trick 1.n == 0 ,時答案是1
            trick 2.二分出來的結果有可能應該輸出No Solution !(具體原因自己考慮一下)

            sgu175:經典
            Let phi(W) is the result of encoding for algorithm:
            1. If the length of W is 1 then phi(W) is W;
            2. Let coded word is W = w1w2...wN and K = N / 2 (rounded down);
            3. phi(W) = phi(wNwN-1...wK+1) + phi(wKwK-1...w1).
            For example, phi('Ok') = 'kO', phi('abcd') = 'cdab'.
            Your task is to find position of letter wq in encoded word phi(W).

            Input
            Given integers N, q (1 <= N <= 10^9; 1<= q <= N), where N is the length of word W.

            Output
            Write position of letter wq in encoded word phi(W).

            Input
            9 4

            Output
            8

            讀完題之后,直覺的想法就是遞歸模擬,復雜度也對,也沒問題,但是就是很容易錯,編碼困難.
            要跟據level的奇偶性,分別討論,有興趣可以嘗試一下,我沒成功......

            google 了以下發現了一個很好的想法,以下是我跟據那個想法寫的遞歸版本
            LL n, q;
            int bin(LL n, LL q)
            {
                if(n <= 1) return 1;
                LL k = n / 2;
                if (q > k) {
                    return bin(n - k, n - q + 1);
                } else {
                    return n - k + bin(k, k - q + 1);
                }
            }

            以如下為例,解釋以下算法
                 分裂  abcdefghi  時
                           /\                                                              
                          /  \                                                             
                       ihgfe dcba                                                          
               對于一個n,k = n / 2:
               如果 q <= k,這時abcd被倒置,如果要在dcba中找d,等價于在abcd中找a
                    也就是k到q的距離成為了新的q
               如果 q >  k,如果要在ihgfe中找h等價于在efghi中尋找f
                    也就是k到n的距離成為了新的q

            然后在體會一下上邊的算法                  
                                                                                           

            posted on 2009-11-23 00:24 schindlerlee 閱讀(1299) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            青春久久| 亚洲欧美伊人久久综合一区二区| 日韩欧美亚洲综合久久| 久久婷婷五月综合色高清| 久久精品免费一区二区三区| 99久久夜色精品国产网站| 一级女性全黄久久生活片免费| 国产成人久久激情91| 色88久久久久高潮综合影院| 国产一区二区三区久久精品| 欧美久久一区二区三区| 久久人妻少妇嫩草AV无码专区| 久久国产AVJUST麻豆| 99国产欧美精品久久久蜜芽| 婷婷久久综合九色综合绿巨人 | 久久这里都是精品| 久久影院亚洲一区| 亚洲午夜福利精品久久| 亚洲精品高清久久| 久久亚洲欧洲国产综合| 久久精品国产亚洲沈樵| 久久亚洲AV成人出白浆无码国产| 久久人人爽人人爽人人片AV东京热| 久久久久亚洲AV片无码下载蜜桃| 少妇被又大又粗又爽毛片久久黑人 | 亚洲一区精品伊人久久伊人| 久久被窝电影亚洲爽爽爽| 久久影院综合精品| 国产精品一区二区久久精品涩爱| 久久精品国产亚洲Aⅴ香蕉| 亚洲国产婷婷香蕉久久久久久| 国产福利电影一区二区三区久久久久成人精品综合 | 久久Av无码精品人妻系列| 狠狠精品久久久无码中文字幕| 国产免费久久精品99久久| 99热精品久久只有精品| 国产精品99久久久久久人| 国产精品久久久久jk制服| 久久99国产综合精品| 久久成人国产精品| 国产一区二区精品久久|