题面
Description
给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
Input
输入文件中仅包含一行两个整数a、b，含义如上所述。
Output
输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。
Sample Input
1 99
Sample Output
9 20 20 20 20 20 20 20 20 20
题解
随便乱搞
其实这一题用递推法是比较好的, 但是我还是写了递归.
非常多的细节需要注意.
#include <cstdio>
#include <cstring>
long long n;
long long pw[30], sum[30], cnt[20];
inline void prework()
{
pw[0] = 1;
for(int i = 1; i < 19; ++ i)
pw[i] = pw[i - 1] * 10;
for(int i = 0; i < 19; ++ i)
sum[i] = pw[i] * (i + 1);
}
long long DFS(int tg, int pos, int lim)
{
if(tg && ! lim)
{
for(int i = 0; i < 10; ++ i)
cnt[i] += sum[pos];
return pw[pos + 1];
}
int L = tg ? 0 : 1, R = lim ? n / pw[pos] % 10 : 10;
if(! pos)
{
if(R == 10)
R = 9;
for(int i = 0; i <= R; ++ i)
++ cnt[i];
return R + 1;
}
long long res = 0;
for(int i = L; i < R; ++ i)
{
DFS(tg || i, pos - 1, 0);
cnt[i] += pw[pos], res += pw[pos];
}
if(! tg)
res += DFS(0, pos - 1, ! R);
if(lim && (tg || R))
{
long long tmp = DFS(tg || R, pos - 1, 1);
cnt[R] += tmp, res += tmp;
}
return res;
}
inline void work(long long _n)
{
memset(cnt, 0, sizeof(cnt));
n = _n;
DFS(0, 18, 1);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("XSY1999.in", "r", stdin);
#endif
prework();
long long L, R;
scanf("%lld%lld", &L, &R);
work(L - 1);
static long long tmp[10];
for(int i = 0; i < 10; ++ i)
tmp[i] = cnt[i];
work(R);
for(int i = 0; i < 10; ++ i)
printf("%lld ", cnt[i] - tmp[i]);
}