Tips：如果你是真的不理解，不要只看，拿出筆來(lái)跟著步驟自己分析。

一、問(wèn)題描述：

一本書(shū)的頁(yè)碼從自然數(shù) 1 開(kāi)始順序編碼直到自然數(shù) n 。書(shū)的頁(yè)碼按照通常的習(xí)慣編排， 每個(gè)頁(yè)碼不含多余的前導(dǎo)數(shù)字 0。 例如， 第 6 頁(yè)用數(shù)字 6 表示而不是 06 或 006等。 數(shù)字計(jì)數(shù)問(wèn)題要求對(duì)給定書(shū)的總頁(yè)碼 n，計(jì)算書(shū)的全部頁(yè)碼分別用到多少次數(shù)字 0、 1、... 、9。

二、問(wèn)題分析：

1. 抽取題意：

簡(jiǎn)單來(lái)說(shuō)就是就是給定一個(gè)數(shù)字 n，統(tǒng)計(jì) 1~n 中用到了多少次數(shù)字0~9。

2. 初步思考：

很容易想到要分?jǐn)?shù)位(如個(gè)位、十位、百位)來(lái)考慮。

為了方便思考，我們做一些約定：

從 0 開(kāi)始考慮，即考慮0~n中用到了多少次數(shù)字0~9，同時(shí)計(jì)算前導(dǎo)0。

用一個(gè)長(zhǎng)度為10的數(shù)組ans[10] 來(lái)存儲(chǔ)各個(gè)數(shù)字的數(shù)量。

從最低位開(kāi)始分析還是最高位開(kāi)始分析？

應(yīng)該從最高位開(kāi)始分析。為什么不先從個(gè)位開(kāi)始考慮呢？因?yàn)閿?shù)字在有除個(gè)位外高位(如十位、百位）的情況下，低位是作用于高位的，低位是高位的補(bǔ)充。在這個(gè)問(wèn)題中，單純的低位并不能說(shuō)明什么。

3. 示例分析：

① 對(duì)于一位數(shù) D 來(lái)說(shuō)，0~D 中用到的數(shù)字個(gè)數(shù)即 0~D 各一次。

② 對(duì)于兩位數(shù) CD 來(lái)說(shuō)，我們先考慮C，即C0，先不管C有多大，當(dāng)C可以為0時(shí)，有00，01, 02, ... , 09 這樣的數(shù)字，則我們知道，C在為0的時(shí)候個(gè)位0~9的數(shù)字各用了一次，同時(shí)C本身被用到了10次；當(dāng)C為1時(shí)，有這樣的數(shù)字10,11,12, ..., 19 ，我們知道 C 為1的時(shí)候個(gè)位0~9的數(shù)字各用了一次，同時(shí)C 被用了10次。

以此類(lèi)推我們知道，C每大一，個(gè)位數(shù)字0~9就都會(huì)被用到1 次。并且本身作為十位的C，C每大一，當(dāng)前C表示的數(shù)字就會(huì)被用到10次。

注意此時(shí)C不能為最大值，因?yàn)镃為最大值的話(huà)按照上述方法考慮，可能超過(guò)CD本來(lái)的值。

再來(lái)考慮D，

當(dāng)C為最大值的時(shí)候，用到的數(shù)字即C0，C1，...，CD ，由此我們知道C為最大值時(shí)C會(huì)被用D+1次，0~D各用了一次。

經(jīng)過(guò)總結(jié)得到，在考慮前導(dǎo)0的情況下，一個(gè)十位數(shù)字CD 0~9的數(shù)字用到的情況如下：

考慮十位得到的 
ans [ 0~9 ] + 1*C  （雖然此時(shí)不能考慮十位最大值，但是有0?。?nbsp;
ans [ 0~C-1 ] + 10^1   
ans [C] + (D+1)  （此時(shí)十位取最大值）
 
考慮個(gè)位得到的
ans[ 0~D ] + 1

③ 有了上面的經(jīng)驗(yàn)，我們來(lái)考慮三位數(shù) ABC

首先對(duì)于百位A，即A00, A01, ... , A99

我們來(lái)統(tǒng)計(jì)一下個(gè)位和十位上的數(shù)字即 00，01，...，99加起來(lái)一共用了多少次0~9

按照上面的想法我們很容易知道，十位從0開(kāi)始每加一，個(gè)位0~9就都會(huì)被用 1 次，同時(shí)十位本身，會(huì)被用到10次。這樣我們知道每個(gè)數(shù)字都被用了 10*1 + 10 次，即20次。

同理并根據(jù)上面的結(jié)論，對(duì)于 000，001，...，999 ，我們知道，如果百位從0開(kāi)始每加一，個(gè)位和十位的數(shù)字組合在一次0~9各會(huì)被用到 20次，同時(shí)作為百位本身，會(huì)被用到100次。這樣我們知道每個(gè)數(shù)字都被用了 10*20 + 10^2 次，即300次。

根據(jù)這個(gè)思想很容易發(fā)現(xiàn)規(guī)律，對(duì)于n 位的數(shù)字 0 到 n 位的數(shù)字9，設(shè) 0~9 各數(shù)字會(huì)被用到的次數(shù)為F（n），則有 F(n) = 10 * F(n-1) + 10^(n-1)，其中F（1）= 1

我們把結(jié)果記入一個(gè)名為dp 的數(shù)組：dp[0] = 0, dp[1]=1, dp[2]=20, dp[3]=300 , ....

這樣我們可以知道

僅考慮百位A，有 
ans [ 0~9 ] + 20*A 
ans [0~A-1] + 10^2 
ans [ A ] + (BC + 1)
 
僅考慮十位，有
ans[ 0~9] + 1*B 
ans[ 0~B-1] + 10^1 
ans[ B ] + (C+1)
 
僅考慮個(gè)位 
ans[ 0~C ] +1
 

4. 總結(jié)規(guī)律：

總結(jié)上方的規(guī)律可知，

在計(jì)入前導(dǎo)0的情況下，要考慮0~n 的數(shù)用到了多少各0~9的數(shù)字，應(yīng)該自高向低逐次取出每一位分析

設(shè)取出的一位為數(shù)字為 X，同時(shí)其位于從個(gè)位數(shù)起的第 Y 位，剩余的低位構(gòu)成的數(shù)字為 Z ，

則答案計(jì)算方法為：

ans[0~9] + dp[Y-1]*X   （當(dāng)X < max 時(shí)考慮低位） 
ans[0~X-1] + 10^(Y-1)  (當(dāng)X < max 時(shí)考慮X) 
ans[X] + (Z+1)    （當(dāng) X = max 時(shí)考慮 X）
 
 
 

經(jīng)檢查，該方法適用于個(gè)位及特殊情況。

5. 解除約定：

我們來(lái)考慮如何除去前導(dǎo)0

首先要明白一件事，前導(dǎo)0只對(duì)0的計(jì)數(shù)產(chǎn)生影響。

那么前導(dǎo)0是在哪里產(chǎn)生的呢？

如果上面說(shuō)的你都明白了，那么很容易知道就在計(jì)算最高位時(shí)的這兩步

ans[0~9] + dp[Y-1]*X   （當(dāng)X < max 時(shí)考慮低位）
ans[0~X-1] + 10^(Y-1)  (當(dāng)X < max 時(shí)考慮X)

在最高位為0的時(shí)候多余出來(lái)的

按照上述方法考慮，設(shè) n 位數(shù)多余出來(lái)的0的個(gè)數(shù)為 G(n)

① 你可以想象把所有數(shù)字都右對(duì)齊，得到：

G (1) = 0

G (2) = 10

G (3) = 10 + 100

......

G (n) = 10^1 + 10^2 + ... + 10^(n-1) ，其中 n>2

② 或者這樣想：

兩位數(shù)可以對(duì)所有個(gè)位數(shù)在十位補(bǔ)0，三位數(shù)可以在兩位數(shù)的基礎(chǔ)上再在百位上對(duì)所有兩位數(shù)再補(bǔ)一個(gè)0，以此類(lèi)推，易知這也是一個(gè)dp

得到 G (n) = G(n-1) + 10^(n-1)，其中 G(1) = 0，n>2

至此，思考部分完成。

三、 編寫(xiě)代碼：

算法時(shí)間復(fù)雜度僅為 O ( log10(n) ) ，接近 O (1) ，吊打暴力 O (nlog10n) 的算法。

#include <bits/stdc++.h> 
using namespace std; 
typedef long long LL; 
LL n;
LL dp[20], ans[20],zeroNum[20];  //zeroNum 用于記錄 n 位數(shù)的前導(dǎo) 0 個(gè)數(shù)
LL pow10[20];  //pow10 用于記錄 10 的次方數(shù)
void makeDp(){
    pow10[0]=1;
    for(int i=1;i<15;i++) pow10[i] = pow10[i-1]*10;
    dp[0]=0,dp[1]=1;
    zeroNum[0]=zeroNum[1]=0;
    for(int i=2;i<15;i++){
        pow10[i]=pow10[i-1]*10;
        zeroNum[i]=zeroNum[i-1] + pow10[i-1];
        dp[i]=10*dp[i-1] + pow10[i-1];
    } 
} 
void solve(LL n,LL ans[]){
    if(n==0){
        ans[0]=1;
        return;
    }
    LL bitNum = log10(n) + 1;
    LL num[20];
    LL nTmp = n;
    for(int i=1;i<=bitNum;i++){
        num[i] = nTmp%10;
        nTmp/=10;
    }
    for(int i=bitNum;i>=1;i--){
        LL x = num[i];
        LL y = i;
        n -= x*pow10[y-1];
        LL z = n;
        for(int j=0;j<10;j++){
            ans[j] += dp[y-1]*x;
        }
        for(int j=0;j<x;j++){
            ans[j]+=pow10[y-1];
        }
        ans[x] += z+1;
    }
    ans[0]-=zeroNum[bitNum];
} 
int main(){
    cin>>n;  
    makeDp();   
    solve(n,ans);
    for(int i=0;i<10;i++){
        if(i==0) printf("%lld\n", ans[i]-1);
        else printf("%lld\n",ans[i]);
    }
}

四、 相關(guān)例題：

洛谷P2602：https://www.luogu.com.cn/problem/P2602

題目描述

給定兩個(gè)正整數(shù) aa 和 bb，求在 [a,b][a,b] 中的所有整數(shù)中，每個(gè)數(shù)碼(digit)各出現(xiàn)了多少次。

輸入格式

僅包含一行兩個(gè)整數(shù) a,ba,b，含義如上所述。

輸出格式

包含一行十個(gè)整數(shù)，分別表示 0\sim 90∼9 在 [a,b][a,b] 中出現(xiàn)了多少次。

輸入輸出樣例

輸入

1  99

輸出

9 20 20 20 20 20 20 20 20 20

說(shuō)明/提示

數(shù)據(jù)規(guī)模與約定

對(duì)于 30% 的數(shù)據(jù)，保證 a≤ b ≤ 10^6；

對(duì)于 100% 的數(shù)據(jù)，保證 1≤a≤b≤10^12。

改改代碼直接交：

#include <bits/stdc++.h>
using namespace std; 
typedef long long LL; 
LL a,b;
LL dp[20], ans1[20],ans2[20],zeroNum[20];
LL pow10[20]; 
void makeDp(){
    pow10[0]=1;
    for(int i=1;i<15;i++) pow10[i] = pow10[i-1]*10;
    dp[0]=0,dp[1]=1;
    zeroNum[0]=zeroNum[1]=0;
    for(int i=2;i<15;i++){
        pow10[i]=pow10[i-1]*10;
        zeroNum[i]=zeroNum[i-1] + pow10[i-1];
        dp[i]=10*dp[i-1] + pow10[i-1];
    } 
} 
void solve(LL n,LL ans[]){
    if(n==0){
        ans[0]=1;
        return;
    }
    LL bitNum = log10(n) + 1;
    LL num[20];
    LL nTmp = n;
    for(int i=1;i<=bitNum;i++){
        num[i] = nTmp%10;
        nTmp/=10;
    }
    for(int i=bitNum;i>=1;i--){
        LL x = num[i];
        LL y = i;
        n -= x*pow10[y-1];
        LL z = n;
        for(int j=0;j<10;j++){
            ans[j] += dp[y-1]*x;
        }
        for(int j=0;j<x;j++){
            ans[j]+=pow10[y-1];
        }
        ans[x] += z+1;
    }
    ans[0]-=zeroNum[bitNum];
}
 
int main(){
    cin>>a>>b;
    makeDp();
    solve(a-1,ans1);
    solve(b,ans2);
    for(int i=0;i<10;i++){
        printf("%lld ",ans2[i]-ans1[i]);
    }
}

以上就是C++數(shù)位DP統(tǒng)計(jì)數(shù)字問(wèn)題示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C++數(shù)位DP統(tǒng)計(jì)數(shù)字的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論