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 閱讀(1310) 評論(0) 編輯收藏引用所屬分類: 解題報告

只有注冊用戶登錄后才能發表評論。


相關文章: zju2589 不重合的n個圓形成的區域 pku3334 二分+求多邊形面積 hdu3264 二分+求兩圓交的面積 zoj2107 最近點對，分治 pku1819 幾何+模擬不難，但是不容易寫對 codeforces contest 16 problem E 比較容易的狀態壓縮動態規劃。 2010-06-21 20:10:05 關于Aho-Corasick (AC) 自動機的三道題目 2010-06-16 12:04:40 pku3528 三維凸包 2010-06-11 00:40 spoj1182 ,dp, number theory, binary search 數位類統計問題 2010-06-08 23:24:36.ural1057 number theory and dp

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Why so serious? --[NKU]schindlerlee

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

導航

統計信息

News

留言簿(5)

隨筆分類(90)

隨筆檔案(105)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜