C++數位DP復雜度統計數字問題示例詳解

Posted on by

Tips：如果你是真的不理解，不要隻看，拿出筆來跟著步驟自己分析。

一、問題描述：

一本書的頁碼從自然數 1 開始順序編碼直到自然數 n 。書的頁碼按照通常的習慣編排， 每個頁碼不含多餘的前導數字 0。 例如， 第 6 頁用數字 6 表示而不是 06 或 006等。 數字計數問題要求對給定書的總頁碼 n，計算書的全部頁碼分別用到多少次數字 0、 1、… 、9。

二、問題分析：

1. 抽取題意：

簡單來說就是就是給定一個數字 n，統計 1~n 中用到瞭多少次數字0~9。

2. 初步思考：

很容易想到要分數位(如個位、十位、百位)來考慮。

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

從 0 開始考慮，即考慮0~n中用到瞭多少次數字0~9，同時計算前導0。

用一個長度為10的數組ans[10] 來存儲各個數字的數量。

從最低位開始分析還是最高位開始分析？

應該從最高位開始分析。為什麼不先從個位開始考慮呢？因為數字在有除個位外高位(如十位、百位）的情況下，低位是作用於高位的，低位是高位的補充。在這個問題中，單純的低位並不能說明什麼。

3. 示例分析：

① 對於一位數 D 來說，0~D 中用到的數字個數即 0~D 各一次。

② 對於兩位數 CD 來說，我們先考慮C，即C0，先不管C有多大，當C可以為0時，有00，01, 02, … , 09 這樣的數字，則我們知道，C在為0的時候個位0~9的數字各用瞭一次，同時C本身被用到瞭10次；當C為1時，有這樣的數字10,11,12, …, 19 ，我們知道 C 為1的時候個位0~9的數字各用瞭一次，同時C 被用瞭10次。

以此類推我們知道，C每大一，個位數字0~9就都會被用到1 次。並且本身作為十位的C，C每大一，當前C表示的數字就會被用到10次。

註意此時C不能為最大值，因為C為最大值的話按照上述方法考慮，可能超過CD本來的值。

再來考慮D，

當C為最大值的時候，用到的數字即C0，C1，…，CD ，由此我們知道C為最大值時C會被用D+1次，0~D各用瞭一次。

經過總結得到，在考慮前導0的情況下，一個十位數字CD 0~9的數字用到的情況如下：

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

③ 有瞭上面的經驗，我們來考慮三位數 ABC

首先對於百位A，即A00, A01, … , A99

我們來統計一下個位和十位上的數字即 00，01，…，99加起來一共用瞭多少次0~9

按照上面的想法我們很容易知道，十位從0開始每加一，個位0~9就都會被用 1 次，同時十位本身，會被用到10次。這樣我們知道每個數字都被用瞭 10*1 + 10 次，即20次。

同理並根據上面的結論，對於 000，001，…，999 ，我們知道，如果百位從0開始每加一，個位和十位的數字組合在一次0~9各會被用到 20次，同時作為百位本身，會被用到100次。這樣我們知道每個數字都被用瞭 10*20 + 10^2 次，即300次。

根據這個思想很容易發現規律，對於n 位的數字 0 到 n 位的數字9，設 0~9 各數字會被用到的次數為F（n），則有 F(n) = 10 * F(n-1) + 10^(n-1)，其中F（1）= 1

我們把結果記入一個名為dp 的數組：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)
 
僅考慮個位 
ans[ 0~C ] +1
 

4. 總結規律：

總結上方的規律可知，

在計入前導0的情況下，要考慮0~n 的數用到瞭多少各0~9的數字，應該自高向低逐次取出每一位分析

設取出的一位為數字為 X，同時其位於從個位數起的第 Y 位，剩餘的低位構成的數字為 Z ，

則答案計算方法為：

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

經檢查，該方法適用於個位及特殊情況。

5. 解除約定：

我們來考慮如何除去前導0

首先要明白一件事，前導0隻對0的計數產生影響。

那麼前導0是在哪裡產生的呢？

如果上面說的你都明白瞭，那麼很容易知道就在計算最高位時的這兩步

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

在最高位為0的時候多餘出來的

按照上述方法考慮，設 n 位數多餘出來的0的個數為 G(n)

① 你可以想象把所有數字都右對齊，得到：

G (1) = 0

G (2) = 10

G (3) = 10 + 100

……

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

② 或者這樣想：

兩位數可以對所有個位數在十位補0，三位數可以在兩位數的基礎上再在百位上對所有兩位數再補一個0，以此類推，易知這也是一個dp

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

至此，思考部分完成。

三、 編寫代碼：

算法時間復雜度僅為 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 位數的前導 0 個數
LL pow10[20];  //pow10 用於記錄 10 的次方數
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]);
    }
}

四、 相關例題：

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

題目描述

給定兩個正整數 aa 和 bb，求在 [a,b][a,b] 中的所有整數中，每個數碼(digit)各出現瞭多少次。

輸入格式

僅包含一行兩個整數 a,ba,b，含義如上所述。

輸出格式

包含一行十個整數，分別表示 0\sim 90∼9 在 [a,b][a,b] 中出現瞭多少次。

輸入輸出樣例

輸入

1  99

輸出

9 20 20 20 20 20 20 20 20 20

說明/提示

數據規模與約定

對於 30% 的數據，保證 a≤ b ≤ 10^6；

對於 100% 的數據，保證 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++數位DP統計數字問題示例詳解的詳細內容，更多關於C++數位DP統計數字的資料請關註WalkonNet其它相關文章！

推薦閱讀：