給定兩個整數(shù) a
和 b
，求 a
和 b
之間的所有數(shù)字中 0～9
的出現(xiàn)次數(shù)。

例如，a=1024，b=1032
，則 a
和 b
之間共有 9
個數(shù)如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出現(xiàn) 10
次，1 出現(xiàn) 10
次，2 出現(xiàn) 7
次，3 出現(xiàn) 3
次等等…

輸入格式
輸入包含多組測試數(shù)據(jù)。

每組測試數(shù)據(jù)占一行，包含兩個整數(shù) a
和 b
。

當(dāng)讀入一行為 0 0 時，表示輸入終止，且該行不作處理。

輸出格式
每組數(shù)據(jù)輸出一個結(jié)果，每個結(jié)果占一行。

每個結(jié)果包含十個用空格隔開的數(shù)字，第一個數(shù)字表示 0 出現(xiàn)的次數(shù)，第二個數(shù)字表示 1 出現(xiàn)的次數(shù)，以此類推。

數(shù)據(jù)范圍
0<a,b<100000000
輸入樣例：
1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0
輸出樣例：
1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247

主要思想就是分情況討論。文章來源地址http://www.zghlxwxcb.cn/news/detail-830676.html

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int get(vector<int> num, int l, int r) // 輔助函數(shù)，返回一個大數(shù)l與r位之間的數(shù)字
{
    int res = 0;
    for(int i = l; i >= r; i -- )
        res = res * 10 + num[i];
    return res;
}

int power10(int x) // 輔助函數(shù)，返回10的x次方
{
    int res = 1;
    while(x -- )
        res *= 10;
    return res;
}

int count(int n, int x) // 計(jì)算1 - n之間，x出現(xiàn)的次數(shù)
{
    if(!n) return 0;
    
    vector<int> num; // 把每一位取出來存下來
    while(n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();
    
    int res = 0;
    for(int i = n - 1 - !x; i >= 0; i -- ) //- ！x的意思是，如果x是0 的話，不枚舉最高位
    {
        if(i < n - 1) // 非最高位的一般情況
        {
            res += get(num, n - 1, i + 1) * power10(i); // 情況1
            if(!x) res -= power10(i); // 特判一下特殊情況（x = 0），例子圖總從001開始算（本來是從000開始算的）
                                      //也就是少一份power10(i)， 減掉即可
        }
        if(num[i] == x) // 情況2.2
            res += get(num, i - 1, 0) + 1; 
        else if(num [i] > x) // 情況2.3
            res += power10(i); 
    }
    return res;
}

int main ()
{
    int a, b;
    while(cin >> a >> b, a || b)
    {
        if(a > b) swap(a, b);
        
        for(int i = 0; i < 10; i ++ )
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }
    
    return 0;
}

到了這里，關(guān)于C++ 動態(tài)規(guī)劃 數(shù)位統(tǒng)計(jì)DP 計(jì)數(shù)問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！