0%

[ZJOI2010] 数字计数

题目

题目链接

题目大意:求出 $[a, b]$ 中的所有整数中每个数字($0$ ~ $9$)出现的次数。$1 \le a, b \le 10^{12}$。

思路

可能是人生唯一一道 ZJOI,这还是十年前的题。

倒是很显然的模板题,状态设成 $f(i, j, k, l, o)$ 表示第 $i$ 位,要求个数的数字为 $j$,$k$ 表示是否枚举的数字是否有上限,$l$ 表示个数,$o$ 表示是否有前导零。

但是这里我第一次记忆化写错了,存的是 f[i][j],其实应该存 f[i][l]。不过后来看题解好像把所有状态都存下来就没事了?不是很懂。

注意开 long long

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

LL f[20][20];
LL ans1[15], ans2[15], dig[20];
LL a, b, len;

LL dfs(int dep, int num, bool lim, LL s, bool zero) {
if ((!dep)) return s;
if ((!lim) && (~f[dep][s]) && zero) return f[dep][s];
LL up = lim ? dig[dep] : 9, ans = 0;
for (int i = 0; i <= up; ++i) {
ans += dfs(dep - 1, num, lim && (i == up), s + (i == num && (zero || i)), zero || i);
}
if ((!lim) && zero) f[dep][s] = ans;
return ans;
}

void solve(LL x, LL *ans) {
len = 0;
memset(dig, 0, sizeof(dig));
while (x) dig[++len] = x % 10, x /= 10;
for (int i = 0; i <= 9; ++i) {
memset(f, -1, sizeof(f));
ans[i] = dfs(len, i, true, 0, false);
}
return ;
}

int main() {
read(a), read(b);
solve(a - 1, ans1), solve(b, ans2);
for (int i = 0; i <= 9; ++i) printf("%lld ", ans2[i] - ans1[i]);
puts("");
return 0;
}