数位dp (分类讨论)
题目
给定两个整数 a和 b,求 a 和 b 之间的所有数字中 0 ∼ 9 的出现次数。
例如,a=1024,b=1032,则 a 和 b 之间共有 99 个数如下:
1024 1025 1026 1027 1028 1029 1030 1031 1032
其中
0
出现 1010 次,1
出现 1010 次,2
出现 77 次,3
出现 33 次等等…
思路
以一个数字abcdefg
举例
假设要计算1再第四位(d) 上出现的次数
分情况讨论:
- 前三位为
000
~abc - 1
, 那么当d取1时候三位efg
就可以随便取值 0 ~ 999 。 所以最后这种情况的方案数就是abc
* 1000; - 前三位为
abc
- 当 d < 1 时 方案是显然为
0
- 当 d == 1 时 那么后三位就可以取到
000
~efg - 1
所以方案数为efg
+ 1; - 当 d > 1 时 那么后三位显然可以取到
000
~999
所以方案数为1000
;
- 当 d < 1 时 方案是显然为
至此讨论完毕 当然没有, 还有边界条件没有讨论:
- 如果这一位要取 0 那么显然它不能出现再首位。
- 如果枚举的时首位 那么第一种情况就不存在。
- 如果当前为取 0 那么第一种情况中 前三位的取值就是从
001
~efg
而不是从000
开始。
实现
- 预处理出1 ~ n 中每个数出现的次数。
-
再用1 ~ b 出现的次数减去 1 ~ a - 1 中出现的次数, 即主要函数
count
。 -
计算方法 则是求出1 ~ n 中 x 出现在每一位上的次数相加
- 就需要先定义一个
num
数组,将每一位分开储存。 - 然后定义两个辅助函数
get
用于求出 l 到 r 表示的数字 (就是把abc
转成数字);第二个辅助函数是计算10的n次方, 其实也可以直接用pow(10,n)
;
上代码
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int get(vector<int> num, int l, int r)
{
int res = 0;
for (int i = r; i >= l; i--)
{
res = res * 10 + num[i];
}
return res;
}
int shi(int x)
{
return pow(10, x);
}
int count(int n, int x)
{
if (!n) return 0;
int res = 0;
vector<int> num;
while (n)
{
num.push_back(n % 10);
n /= 10;
}
n = num.size();
for (int i = n - 1 - !x; i >= 0; i --)
{
if (i < n - 1)
{
res += get(num, i + 1, n - 1) * shi(i);
if (!x) res -= shi(i);
}
if (num[i] == x) res += get(num, 0, i - 1) + 1;
else if (num[i] > x)res += shi(i);
}
return res;
}
int main()
{
int a, b;
while (cin >> a >> b,a ){
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;
}