对于每个 $(a, b)$ ,可以把 $0-9$ 每个数字都处理一遍。
定义count(n, x)
函数,代表 $1-n$ 中, $x$ 出现的次数。
那么, count(b, x) - count(a - 1, x)
即为答案。
如何快速的求出 count(n, x)
呢?
先假设 $n$ 是个 $7$ 位数 $(n = abcdefg)$,求 $1$ 出现的次数。
可以枚举每一位 $x$ 出现的次数,然后求和。
假设现在枚举到第 $4$ 位数,也就是 $d$ 所在的位置。
答案就是所有合法的 $xxx1yyy$ 的数量。
这里分情况进行讨论。
1. $000 <= xxx < abc$
这种情况下,无论 $yyy$ 选什么都一定合法。
所以贡献为 $abc * 1000$ ( $xxx$ 可以是 $000-abc$ , $yyy$ 可以是 $000-999$ )。
2. $xxx = abc$
在此基础上,还需继续深入讨论。
2.1 $d < 1$
这种情况下无论 $yyy$ 选什么都不合法,所以有 $0$ 种可能。
2.2 $d = 1$
这种情况下 $yyy$ 的取值范围在 $000-efg$ ,所以贡献为 $efg+1$ 。
2.3 $d > 1$
这种情况下 $yyy$ 的取值范围在 $000-999$ ,所以贡献为 $1000$ 。
以此类推,其它情况可以照葫芦画瓢,但还有一些特殊情况。
特殊情况一:当前枚举的位置是最高位
这样1.就不存在了,也就为 $0$ 。
特殊情况二:当前找的数字为 $0$
在这种情况下,2.部分不变,需要注意1.部分。
如果 $xxx=000$ 的话,当前看的这一位和左面都会被忽略掉,所以 $xxx$ 的取值范围应变为 $001-abc$ ,贡献为 $(abc-1)*1000$ 。
最后附上AC代码。
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int get(vector<int> num,int l,int r)
{
int ans = 0;
for (int i=l;i>=r;i--)
ans = ans * 10 + num[i];
return ans;
}
int Pow(int x)
{
int ans = 1;
while (x--)
ans *= 10;
return ans;
}
int count(int n,int x)
{
if (n == 0)
return 0;
vector<int> num;
while (n)
{
num.push_back(n % 10);
n /= 10;
}
n = num.size() - 1;
int ans = 0;
for (int i = n - (x == 0); i >= 0; i --)
{
if (i != n)
{
ans += get(num, n, i + 1) * Pow(i);
if (x == 0)
ans -= Pow(i);
}
if (num[i] == x)
ans += get(num, i - 1, 0) + 1;
else if (num[i] > x)
ans += Pow(i);
}
return ans;
}
int main()
{
for (;;)
{
int a,b;
scanf("%d%d",&a,&b);
if (a == 0)
break;
if (a > b)
swap(a, b);
for (int i=0;i<9;i++)
printf("%d ", count(b, i) - count(a - 1, i));
printf("%d\n", count(b, 9) - count(a - 1, 9));
}
return 0;
}