[SMOJ1772]數頁碼

這題也是個好題，做法挺多的。

做法一：暴力算。

時間複雜度： O(n×len) 。

得分：40。

代碼：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

int calc(int x) {
    int sum = 0;
    while (x) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int n;

int main(void) {
    freopen("1772.in", "r", stdin);
    freopen("1772.out", "w", stdout);

    scanf("%d", &n);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += calc(i);

    printf("%d\n", ans);

    return 0;
}
           

做法二：

其實[0,9]，[0,99]，[0,999]……這些都是有規律可循的。那麼可以把前面這段有規律的算出來，後面多出來的部分再暴力。

前面的規律是：[0,9]時1~9各出現1次（0對總和不作貢獻，不予考慮，下同）

[0,99]時，個位1~9各出現10次，十位1~9各出現10次，總計各出現20次

[0,999]時，根據乘法原理，個位1~9各出現10*10=100次，十位和百位同理，總計各出現300次

于是不難得到，對于 [0,10k−1] ，數字1~9的出現次數都為 k×10k−1 。

然而，剩下部分的暴力卻也是比較麻煩的，因為 n 最大為 109，如果 n=999999998 ， 單是暴力部分就超過 108 ，會 TLE。

時間複雜度： O(n−10⌊lgn⌋) 。

得分：40。

代碼：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

int calc(int x) {
    int sum = 0;
    while (x) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int n;

int main(void) {
    freopen("1772.in", "r", stdin);
    freopen("1772.out", "w", stdout);

    scanf("%d", &n);
    if (n <= 99) { //小資料單獨讨論一下
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += calc(i);
        printf("%d\n", ans);
        return 0;
    }
    int cnt = 1, Pow = 1;
    int i;
    for (i = 9; i <= n; ) {
        if (i * 10 + 9 > n) break; else i = i * 10 + 9;
        Pow *= 10;
        cnt = cnt * 10 + Pow;
    }
    //printf("%d\n", cnt);

    int ans = 0;
    for (int i = 1; i < 10; i++) ans += cnt * i;
    for (int j = i + 1; j <= n; j++) ans += calc(j);

    printf("%d\n", ans);

    return 0;
}
           

但其實我們都很明白，資料這麼大，凡是線性時間的做法都是耍流氓。正解隻能是常數時間。

正解：

可以根據位數對給定數字進行分解，以34567為例：

先考慮 n 個數中個位上分别是1～9的個數，先來看34560，顯然34560裡個位是1的數有3456個，2到9也是3456個。

那麼沒統計的數字就是34560，34561，34562，34563，34564，34565，34566，34567這8個，顯然個位是1~7的又各增加1個。

再來看十位：類似的來看34500，則十位是1~9的數各有3450個，剩下還有34501～34567，則十位是1～5的個數分别增加10個，十位是6的增加8個。

以此類推。

時間複雜度：O(len)。

得分：100。

重點部分：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>

using namespace std;

int getws(int x) {
    int ret = 0;
    while (x) {
        x /= 10;
        ++ret;
    }
    return ret;
}

int n;
long long cnt[10];

int main(void) {
    freopen("1772.in", "r", stdin);
    freopen("1772.out", "w", stdout);

    scanf("%d", &n);
    int ws = getws(n); //求出位數
    long long Pow = 1; //p=10^k，當然這個k沒有顯式儲存
    //下面以k=2推算，也就是考慮十位的情況
    while (ws--) {
        Pow *= 10;
        long long t = n / Pow * Pow; //相當于把最後k位清0，例如34567，這裡得到34500
        for (int i = 1; i < 10; i++) //這部分是統一的，都能增加3450個。
        //因為當十位确定之後，前面五位有345種，後面個位為0~9，是以根據乘法原理共3450種
            cnt[i] += t / 10;
        t = n - t; //多出來的部分：34567-34500=67
        long long x = t / (Pow / 10); //得到十位最大為6
        for (int i = 1; i < x; i++) //對于前面的1~5，它後面的k-1位還是可以任意取的
            cnt[i] += Pow / 10;
        cnt[x] += t - x * (Pow / 10) + 1; //而十位為6就最多隻能取0~7這8種
    }

    long long ans = 0;
    for (int i = 0; i < 10; i++) ans += cnt[i] * i;

    printf("%lld\n", ans);

    return 0;
}
           

想的時候比較直覺，當然寫起代碼來有些式子要推還是感覺有點煩。。程式設計要有耐心，恒心，毅力！！！