Description
给出一段区间 a-b ,统计这个区间内 0-9 出现的次数。
比如 10-19,1 出现 11 次(10, 11, 12, 13, 14, 15, 16, 17, 18, 19,其中 11 包括 2 个 1 ),其余数字各出现 1 次。
Input
两个数 a,b(1 <= a <= b <= 10^18)
Output
输出共 10 行,分别是 0-9 出现的次数
Input示例
10 19
Output示例
1
11
1
1
1
1
1
1
1
1
思路
很容易想到该题的结论满足区间减法,于是我们只需要分别计算 $[0,a-1]$ 以及 $[0,b]$ 的结果,相减既是答案。
我们考虑从一个数 $x$ 的低位往高位开始枚举,对于第 $k$ 位我们分情况进行讨论。
假设 $x=12345$ ,$k$ 指向数字 $3$ 的位置,则此时 $pre = 12, after=45,tmp=100$ 。
我们枚举 $i$ 从 $0-9$:
- 当前数字小于 $i$ ,即 $i\in[4,9]$ ,此时高位的变化范围可以是 $[0,11]$ ,共 $pre \times tmp$ 种方案
- 当前数字大于 $i$ ,即 $i\in[0,2]$ ,此时高位的变化范围可以是 $[0,12]$ ,共 $(pre+1)\times tmp$ 种方案
- 当前数字等于 $i$ ,即 $i=3$ ,此时高位的变化范围可以是 $[0,12]$ ,当且仅当高位等于 $12$ 时低位最多取到 $45$ ,因此共有 $pre \times tmp + after + 1$ 种方案
特殊的当 $i=0$ 时且高位为 $0$ 时,显然这种情况是不允许的,因此我们需要减去一个 $tmp$ 。
AC 代码
#include <bits/stdc++.h>
#define IO \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
LL ans[10];
void solve(LL n, int sign) {
LL cur, pre, after, tmp = 1, tn = n;
while (n) {
cur = n % 10;
pre = n / 10;
after = tn - n * tmp;
for (int i = 0; i < 10; i++) {
if (cur > i)
ans[i] += (pre + 1) * tmp * sign;
else if (cur < i)
ans[i] += pre * tmp * sign;
else
ans[i] += (pre * tmp + after + 1) * sign;
}
ans[0] -= tmp * sign;
tmp *= 10;
n /= 10;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
IO;
#endif // ONLINE_JUDGE
LL l, r;
cin >> l >> r;
solve(l - 1, -1);
solve(r, 1);
for (int i = 0; i < 10; i++) {
cout << ans[i] << endl;
}
return 0;
}