数位DP真是有够自闭的
懵逼的 题目
BZOJ
扯淡的 题解
每次感觉只是个细节问题 然后就改不了了...
一开始我用f[i][0 : 1][0 : 1][0 : 9]表示:
当前在第i位, 是否还是前导0, 是否卡上界,
0 ~ 9每个数码的个数
然后发现在更新的时候我要加的是[符合前i个条件的数的个数]...但是我并没有记录...
后来参悟了一下zyf2000学姐的写法
似乎也只有本校的学长学姐用数组的写法了
枚举当前要处理的数位\(x\)
f[i][times][0 : 1][0 : 1]代表当前在第i位,
有times个\(x\),
是否卡上界, 是否是前导0的数的个数
这样在更新的时候我们就可以搞数的个数了...
而且还有一个地方就是尽量的减少DP数组的状态, 毕竟DP是对状态的压缩
当然是要越简单越好了...枚举\(x\)减少了肥肠大的代码复杂度...
沙茶的 代码
Before
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define MAXL (15 + 5)
using namespace std;
void solve(LL x, LL* ans) {
LL f[MAXL][2][2][11];
int a[MAXL];
memset(f, 0, sizeof(f));
a[0] = 0;
while (x) a[++a[0]] = x % 10ll, x /= 10ll;
f[a[0] + 1][1][1][10] = 1;
for (int i = a[0]; i >= 1; i--)
for (int is0 = 0; is0 <= 1; is0++)
for (int u = 0; u <= 1; u++)
if (f[i + 1][is0][u][10])
for (int nn = 0; nn <= 9; nn++) {
int uu = u & (nn == a[i]), nis = is0 & (!nn);
if (u && nn > a[i]) continue;
f[i][nis][uu][10] = 1;
if (nis) continue;
for (int gg = 0; gg <= 9; gg++)
f[i][nis][uu][gg] += f[i + 1][is0][u][gg];
++f[i][nis][uu][nn];
}
for (int is0 = 0; is0 <= 1; is0++)
for (int u = 0; u <= 1; u++)
if (f[1][is0][u][10])
for (int n = 0; n <= 9; n++)
ans[n] += f[1][is0][u][n];
}
int main() {
LL a, b, ax[MAXL], bx[MAXL];
memset(ax, 0, sizeof(ax));
memset(bx, 0, sizeof(bx));
scanf("%lld%lld", &a, &b);
solve(b, bx);
solve(a - 1, ax);
for (int i = 0; i <= 9; i++)
printf("%lld ", bx[i] - ax[i]);
puts("");
return 0;
}
|
After
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define MAXL (15 + 5)
#define MAXZ (10)
using namespace std;
LL solve(LL x, int dqw) {
int a[MAXL];
a[0] = 0;
while (x) a[++a[0]] = x % 10, x /= 10;
LL f[MAXL][MAXL][2][2];
memset(f, 0, sizeof(f));
f[a[0] + 1][0][1][1] = 1;
for (int i = a[0]; i >= 1; i--)
for (int times = 0; times < MAXL; times++)
for (int u = 0; u <= 1; u++)
for (int is0 = 0; is0 <= 1; is0++)
if (f[i + 1][times][u][is0]) {
for (int nn = 0; nn <= 9; nn++) {
if (u && nn > a[i]) continue;
int uu = (u && nn == a[i]), nis = (is0 && !nn);
if (is0)
++f[i][nn == dqw][uu][nis];
else
f[i][times + (nn == dqw)][uu][nis] += f[i + 1][times][u][is0];
}
}
LL re = 0;
for (int times = 0; times < MAXL; times++)
for (int u = 0; u <= 1; u++)
re += f[1][times][u][0] * times;
return re;
}
int main() {
LL a, b;
scanf("%lld%lld", &a, &b);
for (int i = 0; i < 9; i++)
printf("%lld ", solve(b, i) - solve(a - 1, i));
printf("%lld", solve(b, 9) - solve(a - 1, 9));
return 0;
}
|
By 准备退役旅游的 Cansult