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 ，
则答案计算方法为：
|
1
2
3
4
5
6
|
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) 的算法。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#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。
改改代码直接交：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#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统计数字的资料请关注服务器之家其它相关文章！
原文链接：https://blog.csdn.net/sinat_40471574/article/details/106692542
