如何解決C++數(shù)位DP復雜度統(tǒng)計數(shù)字問題

小編給大家分享一下如何解決C++數(shù)位DP復雜度統(tǒng)計數(shù)字問題，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

一、問題描述：

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

二、問題分析：

1. 抽取題意：

簡單來說就是就是給定一個數(shù)字 n，統(tǒng)計 1~n 中用到了多少次數(shù)字0~9。

2. 初步思考：

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

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

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

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

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

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

3. 示例分析：

① 對于一位數(shù) D 來說，0~D 中用到的數(shù)字個數(shù)即 0~D 各一次。

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

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

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

再來考慮D，

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

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

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

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

首先對于百位A，即A00, A01, ... , A99

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

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

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

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

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

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

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

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

設(shè)取出的一位為數(shù)字為 X，同時其位于從個位數(shù)起的第 Y 位，剩余的低位構(gòu)成的數(shù)字為 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）

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

5. 解除約定：

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

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

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

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

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

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

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

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

G (1) = 0

G (2) = 10

G (3) = 10 + 100

......

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

② 或者這樣想：

兩位數(shù)可以對所有個位數(shù)在十位補0，三位數(shù)可以在兩位數(shù)的基礎(chǔ)上再在百位上對所有兩位數(shù)再補一個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 位數(shù)的前導 0 個數(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

題目描述

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

輸入格式

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

輸出格式

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

輸入輸出樣例

輸入

1  99

輸出

9 20 20 20 20 20 20 20 20 20

說明/提示

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

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

對于 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)計數(shù)字問題”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！