用的解法和dp无关,用分类讨论的思想当成一个数学问题来处理
思路:统计数字x在某一位上出现的次数,把每一位的出现次数加起来就是这个数的总出现次数
那么给定一个l,就可以算出[0, l]中x的出现次数,至于求[l, r]出现的次数,可以先求出[0, l-1]出现的次数,再求
[0, r]的出现次数,相减就可以了
和着个题非常类似leetcod 233. 数字 1 的个数
/*
计算1-n中第x出现的次数,先考虑x = 1 ~ 9
思路:依次计算x在每一位中出现的次数
以x = 1为例,依次计算x在每一位出现的次数
现计算1在第4位出现的次数,?把这个数字分割成了[l, i, r]三部分
123 ? 3210
1. ? > 1 时 前三位可以取0-122, 后四位可以取0-9999,总共123*1e4 种
前三位取123时,?处取1时,后四位可以取0-9999,共1额e4种
这种情况共 124*1e4种
2. ? = 1 时 前三位取0-122时,后四位可以取0-9999,总共123*1e4 种
前三位取123时,后四位可以取0-3210,共3211种
这种情况共 123*1e4 + 3211
3. ? < 1时 如果要想第四位取1,前三位只能取0-122,后四位共有123 * 1e4种
现考虑特殊情况x = 0, 当前数字为123?3210, 0在?位置出现的次数
1. 当? > 0 时,前三位取1-122时,后四位可以取0-9999 (前三位取0时这种情况无效)
前三位取123时, 后四位可取0-9999
总共123*1e4种
2. 当? = 0 时,为了保证这个数字是有效的,前三位取1-123
前三位为1-122时,总共122*1e4种
前三位取123时,后四位可取0-3210
总共122*1e4 + 3211种
*/
#include<iostream>
using namespace std;
int a, b;
//计算数1-n中,数字x的的出现次数, x = 0 ~ 9
int count(int n, int x)
{
int cnt = 0, rate = 1;
while(rate <= n){
int i = n / rate % 10;
int l = n / 10 / rate;
int r = n % rate;
if(i > x) {
cnt += (l + !!x)*rate;
}
else if(i == x) {
cnt += (l - !x) * rate + r + 1;
}
else {
cnt += l * rate;
}
rate *= 10;
}
return cnt;
}
int main(){
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;
}