• <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)  編輯 收藏 引用 所屬分類: 解題報告

            精品多毛少妇人妻AV免费久久| 国产色综合久久无码有码| 亚洲中文久久精品无码ww16| 亚洲国产精品无码久久青草| 久久AV高潮AV无码AV| 国产精品久久久久影视不卡 | 欧洲精品久久久av无码电影 | 亚洲一区精品伊人久久伊人| 免费一级做a爰片久久毛片潮| 久久精品国产亚洲av麻豆蜜芽| 亚洲欧美日韩久久精品第一区| 久久精品国内一区二区三区| 色婷婷久久综合中文久久一本| 成人久久免费网站| 欧美丰满熟妇BBB久久久| 91精品国产乱码久久久久久| 国产精品日韩欧美久久综合| 97久久精品午夜一区二区| 国产巨作麻豆欧美亚洲综合久久| 中文成人无码精品久久久不卡 | 精品免费久久久久久久| 开心久久婷婷综合中文字幕| 久久精品国产亚洲αv忘忧草| 好属妞这里只有精品久久| 18禁黄久久久AAA片| 久久精品无码一区二区三区日韩| 国产精品免费福利久久| 久久婷婷五月综合97色直播| 99久久er这里只有精品18| 久久男人AV资源网站| 国内精品伊人久久久久| 18岁日韩内射颜射午夜久久成人| 久久精品二区| 伊人久久精品线影院| 国产99久久久久久免费看| 性做久久久久久久久浪潮| 久久精品一区二区三区中文字幕 | 91精品国产综合久久香蕉| 久久久久久久波多野结衣高潮| 国产精品嫩草影院久久| A级毛片无码久久精品免费|