问题
求区间内的所有数字中 $0$ ~ $9$ 分别出现的次数
数位dp确实让人脑瓜子疼
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
/*
n = abcdefg
枚举每一位,假设此时枚举的第四位
1. 001~abc-1 x 000~999 即此时 d = x
2. abc x
2.1 d < x, 0
2.2 d = x, 000~efg
2.3 d > x, 000~999
*/
//求l到r位对应的数
int get(vector<int> num, int l, int r)
{
int res = 0;
for(int i = l; i >= r; i--)
res = res * 10 + num[i];
return res;
}
//求10的x次方
int power10(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;
//逆序存的,从最后即高位开始枚举
//求0出现次数时,最高位不能为0,所以需要从第二高位开始枚举
for(int i = n - 1 - !x; i >= 0; i--)
{
if(i < n-1)
{
//000~abc-1共abc种
res += get(num, n-1, i+1)*power10(i);
//x等于0时,枚举的那一位为0,那么前面的abc就不能为000了
/*
举个例子:
当x不为0,假定为1时,这里算的就是x000~x999,1x000~1x999,2x000~2x999,...
(abc-1)x000~(abc-1)x999,这就是000~abc-1的情况
而x为0时:x000~x999这种情况就不合法,需要减去,即001~abc-1的情况
*/
if(!x) res -= power10(i);
}
if(num[i] == x)
{
res += get(num, i-1, 0) + 1;
}
else if(num[i] > x) res += power10(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;
}
9494