数位统计dp
参考 这位犇犇的题解
直接看代码:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath> // pow()
using namespace std;
int dgt(int x) // 获取x的位数
{
int res = 0;
while(x)
{
res++;
x /= 10;
}
return res;
}
int count(int n, int i)
{
int res = 0, d = dgt(n);
for(int j = 1; j <= d; ++j)
{
// p是j后的位数,l是y总视频里的abc,r是efg,dj是j位上的数
// abc是j前面的数,不一定是三位数,efg同理
int p = pow(10, j - 1), l = n / p / 10, r = n % p, dj = n / p % 10;
// case 1: xxx < abc
// if(i非0)
// {
// 000 ~ abc - 1
// }
// else if(i是0)
// {
// 不能全是前导0:
// 001 ~ abc - 1
// }
i ? res += l * p : res += (l - 1) * p;
// case 2: xxx == abc, 考虑yyy的情况
// if(i > dj) 不存在
// else if(i == dj) 只考虑后面的efg, 即000 ~ efg
// else if(i < dj) 后面efg随便取, 即000 ~ 999
if(i == dj)
{
res += r + 1;
}
else if(i < dj)
{
res += p;
}
}
return res;
}
int main()
{
int a, b;
while(cin >> a >> b, a) // 正常数据a≠0
{
if(a > b) swap(a, b); // a可能小于b
for(int i = 0; i <= 9; i++) printf("%d ", count(b, i) - count(a - 1, i)); // 和前缀和一个意思
puts(""); // 换行
}
return 0;
}