数据结构与算法学习笔记----数位统计DP

数据结构与算法学习笔记----数位统计DP

@@ author: 明月清了个风 @@ first publish time: 2025.2.16

ps⭐️一道数位统计DP题目，比较复杂，代码中需要注意的点比较多，关键的思路是分情况讨论

Acwing 338. 计数问题

[原题链接](338. 计数问题 - AcWing题库)

给定两个整数 a a a和 b b b，求 a a a和 b b b之间的所有数字中 0 ∼ 9 0 \sim 9 0∼9的出现次数。

例如， a = 11024 , b = 1032 a = 11024, b = 1032 a=11024,b=1032，则 a a a和 b b b之间的 9 9 9个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中0出现 10 10 10次，1出现 10 10 10次，2出现 7 7 7次，3出现 3 3 3次等等。。。

输入格式

输入包含多组测试数据。

每组测试数据占一行，包含两个整数 a a a和 b b b。

当读入一行为0 0时，表示输入终止，且该行不作处理。

输出格式

每组数据输出一个结果，每个结果占一行。

每个结果包含十个用空格隔开的数字，第一个数字表示 0出现的次数，第二个数字表示1出现的次数，以此类推。

数据范围

0 < a , b < 100000000 0 < a, b < 100000000 0<a,b<100000000

思路

很明显不能直接暴力做，数据范围太大了，这题都关键思路是分情况讨论，并且用到了类似前缀和的思想，对于 [ a , b ] [a,b] [a,b]中某个数 x x x出现的次数，可以通过计算 [ 1 , b ] [1,b] [1,b]中出现次数- [ 1 , a − 1 ] [1,a - 1] [1,a−1]中出现次数计算。

计算的思路是求出数 x x x在每一位上出现的次数，然后进行下面的分情况讨论：

假设我们的 n n n是 a b c d e f g abcdefg abcdefg，统计的数是 x > 0 x > 0 x>0，当前统计其在第四位的数的数量

高位 000 ∼ a b c − 1 000 \sim abc - 1 000∼abc−1，第四位取 x x x，那么后面的 e f g efg efg可以随便取，因此这一类中共有 a b c ∗ 1000 abc * 1000 abc∗1000个当前三位等于 a b c abc abc，对 n n n的第四位进行讨论 若 d < x d < x d<x，那么范围内不可能有数在这一位是 x x x，因此为 0 0 0。若 d = x d = x d=x，则后三位就可以取到 000 ∼ e f g 000 \sim efg 000∼efg，共 e f g + 1 efg + 1 efg+1种。若 d > x d > x d>x，则后三位可以取到 000 ∼ 999 000 \sim 999 000∼999，也就是 1000 1000 1000种。

还有一种特殊的就是要统计的是 0 0 0的出现次数，这时第一类情况就有变化，因为不能有前导 0 0 0，否则就会出现 0000 e f g 0000efg 0000efg，因此需要将高位从 001 001 001开始枚举。

当然如果统计的是数 x x x在第一位出现的次数，第一类就不存在了，因此需要判断，代码中需要注意。

同时，如果统计的是 0 0 0，那么枚举需要从第二位开始。

代码 #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> using namespace std; int get(vector<int> num, int r, int l) { int res = 0; for(int i = r; i >= l; i --) { res = res * 10 + num[i]; } return res; } int pow10(int x) { int res = 1; while(x --) res *= 10; return res; } int count(int n, int x) { if(!n) return 0; vector<int> num; while(n) { num.push_back(n % 10); n /= 10; } n = num.size(); int res = 0; for(int i = n - 1 -!x; i >= 0; i --) // 枚举这个数在哪一位上，从高位开始 { if(i < n - 1) // 只有不在最高位的时候才有第一类情况 { res += get(num, n - 1, i + 1) * pow10(i); if(!x) res -= pow10(i); } if(num[i] == x) res += get(num, i - 1, 0) + 1; else if(num[i] > x) res += pow10(i); } return res; } int main() { int a, b; while(cin >> a >> b, a || b) { if(a > b) swap(a,b); for(int i = 0; i < 10; i ++) cout << count(b, i) - count(a - 1, i) << ' '; cout << endl; } return 0; }