溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下如何解決C++數位DP復雜度統計數字問題，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！
一本書的頁碼從自然數 1 開始順序編碼直到自然數 n 。書的頁碼按照通常的習慣編排， 每個頁碼不含多余的前導數字 0。 例如， 第 6 頁用數字 6 表示而不是 06 或 006等。 數字計數問題要求對給定書的總頁碼 n，計算書的全部頁碼分別用到多少次數字 0、 1、... 、9。
簡單來說就是就是給定一個數字 n，統計 1~n 中用到了多少次數字0~9。
很容易想到要分數位(如個位、十位、百位)來考慮。
為了方便思考，我們做一些約定：
從 0 開始考慮，即考慮0~n中用到了多少次數字0~9，同時計算前導0。
用一個長度為10的數組ans[10] 來存儲各個數字的數量。
從最低位開始分析還是最高位開始分析？
應該從最高位開始分析。為什么不先從個位開始考慮呢？因為數字在有除個位外高位(如十位、百位）的情況下，低位是作用于高位的，低位是高位的補充。在這個問題中，單純的低位并不能說明什么。
① 對于一位數 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
總結上方的規律可知，
在計入前導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）
經檢查，該方法適用于個位及特殊情況。
我們來考慮如何除去前導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復雜度統計數字問題”有了一定的了解，如果想了解更多相關知識，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
