题目描述
可能是我学的不够深入吧,感觉更像是贪心的内容qwq
将每一位出现某数字的次数分别计算,就让要求的数字为 x 吧
对于每一位 x 出现的次数,是当该位为 x 时,从 0 到该数可能出现的情况
当我们要求某一位 x 出现的次数时
需要生成这样几个数,待求数位上的数字 di
di 之前的数,我们叫它前缀数,后面的叫它后缀数
该次数可以看成两部分
第一部分是 < 0 ~ 前缀数 - 1 > x < 0 ~ 99... > 的个数(若 x 为 0 ,只能从 1 开始)
第二部分是 <前缀数> x < 0 ~ 后缀数 > 的个数 (如果 di 比 x 大,后缀可以任取 0 ~ 99... 的数)
当 x 为 0 时,要想让该位上的数字为 x,前面必须不为 0,因为不同长度的前缀 0 的相同数会被看成不同情况,但实际上前缀 0 的个数对于数的表达没有意义
代码
// 模板来自 Alicia编程果果
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int get(int n)
{
int res = 0;
while (n) res ++, n /= 10;
return res;
}
int count(int n, int x)
{
int res = 0, dgt = get(n); // digit的缩写
for (int i = 1; i <= dgt; i ++)
{
int p = pow(10, dgt - i), l = n / p / 10, r = n % p, di = n / p % 10;
if (x) res += l * p; // 如果要找的数不是 0,加上 0 ~ 前缀数 - 1 出现次数
else res += (l - 1) * p; // 如果要找的数是 0,由于前面不能为 0,加上 1 ~ 前缀数 的出现次数
if (x == di) res += r + 1; // 第 i 位数字若等于 x,加上 0 ~ 尾数 的个数
else if (x < di) res += p; // 第 i 位数字若大于 x,加上 0 ~ 99... 的个数
}
return res;
}
int main()
{
int a, b;
while (cin >> a >> b, a)
{
if (a > b) swap(a, b);
for (int i = 0; i <= 9; i ++) cout << count(b, i) - count(a - 1, i) << ' ';
cout << endl;
}
return 0;
}