2019.8.9 集训解题报告

啦啦啦~


考试

粉刷匠

这个粉刷匠不是第一天 A 组的粉刷匠,不会用 $dp$ 的喔死磕半个多小时才把方程列出来,应该是:

我不知道是不是对的,最后收集答案时使用 $dfs$ 枚举,只加了一个最优化剪枝。


好的,是错的。QAQ

今天这道提高 B 组的 T1 在洛谷的难度是:这让我的心态有了一点 小小 的变化 qwq

这题预处理一下就可以转换成一个背包问题,因为我不会,所以我也不知道 $dalao$ 们是怎么想出来的,只能原样照搬 qwq

首先设计状态:

  • $f[i][k]$ :表示前 $i$ 条木板一共粉刷 $k$ 次后的最大合法格子数
  • $w[i][j][k]$ :表示在第 $i$ 条木板上涂完前 $j$ 个格子后用了 $k$ 次粉刷的最大合法格子数

那么只需要预处理出 $w[i][j][k]$ ,就可以像背包问题一样转移 $f[i][j]$ 了。

对于 $f[i][j]$ 的转移,是显而易见的(在处理出 $w[i][j][k]$ 以后):

其中:

  • $m$ 是固定的,表示一行多少个
  • $k$ 是不一定的,因为不知道刷多少次,所以要枚举一遍

对于 $w[i][j][k]$ 的预处理,在枚举 $i$ 、$j$ 、$k$ ,更新出最大值。对于计算更新后作出的贡献,可以加一个前缀和来方便计算。

设 $sum[i][j]$ 等于第 $i$ 行,前 $j$ 个蓝色格子(蓝色是 1 ,方便加)的个数。

那么对于一个区间中的红色格子:

对于一个区间的蓝色格子:

那么对于 $w[i][j][k]$ 的处理:

然后就完成了~~

$Test’s$ $Code$:0%

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
const int MAXN = 50 + 5;
const int MAXM = 50 + 5;
const int MAXT = 25e2 + 5;

int n, m, T, ans;
int f[MAXN][MAXM][MAXT], col[MAXN][MAXM][MAXT];
int g[MAXN][MAXM], s[MAXN], Max[MAXN];

void dfs (int i, int k, int cnt) {
if (i > n) {
ans = max (ans, cnt);
return;
}
if (cnt + s[i] <= ans) {
return;
}
if (i == n) {
dfs (i + 1, 0, cnt + f[i][m][k]);
return;
}

for (int j = 0; j <= k; j++) {
dfs (i + 1, k - j, cnt + f[i][m][j]);
}
return;
}

int main() {
scanf ("%d%d%d", &n, &m, &T);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >> ch;
g[i][j] = ch - '0';
}
}

for (int k = 1; k <= T; k++) {
for (int i = 1; i <= n; i++) {
if (k == 1) {
f[i][1][k] = 1;
col[i][1][k] = g[i][1];
}
for (int j = k + 1; j <= m; j++) {
int x = f[i][j - 1][k] + (g[i][j] == (col[i][j - 1][k]) ? 1 : 0);
int y = f[i][j - 1][k - 1] + (g[i][j] == (1 - col[i][j][k - 1]) ? 1 : 0);
if (x > y) {
f[i][j][k] = x;
col[i][j][k] = col [i][j - 1][k];
}
else {
f[i][j][k] = y;
col[i][j][k] = 1 - col[i][j - 1][k - 1];
}
}
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout <<i<<" "<<j<<endl;
for (int k = 1; k <= T; k++) {
cout <<f[i][j][k]<<" ";
}
cout <<endl;
}
cout <<endl;
}

for (int i = 1; i <= n; i++) {
for (int k = 1; k <= T; k++) {
Max[i] = max (Max[i], f[i][m][k]);
}
}

for (int i = n; i >= 1; i--) {
s[i] = s[i + 1] + Max[i];
}

dfs (1, T, 0);

printf ("%d\n", ans);
return 0;
}

$Fixed$ $Code$:100%

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 50 + 5;
const int MAXM = 50 + 5;
const int MAXT = 25e2 + 5;

int n, m, t, a[MAXN][MAXM];
int f[MAXN][MAXT], w[MAXN][MAXM][MAXT], sum[MAXN][MAXM];

int main() {
scanf ("%d%d%d", &n, &m, &t);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >>ch;
a[i][j] = ch - '0';
sum[i][j] = sum [i][j - 1] + a[i][j];
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= m; k++) {
for(int l = k - 1; l <= j - 1; l++) {
w[i][j][k] = max (w[i][j][k], w[i][l][k - 1] + max (sum[i][j] - sum[i][l], (j - l) - (sum[i][j] - sum[i][l])));
}
}
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= t; j++) {
for (int k = 0; k <= min (j, m); k++) {
f[i][j] = max (f[i][j], f[i - 1][j - k] + w[i][m][k]);
}
}
}

printf ("%d\n", f[n][t]);
return 0;
}

迷路

什么倍增 + $Floyd$ + 矩阵快速幂???

等我学完矩阵快速幂再说 QAQ

游戏

这道题又是被几天前那个小学生巨佬讲解的 qwq,我要自闭了…..

题目要一个字符串还原,可以发现每一个数字都是会回到起点的,也就是一个循环,要想要他们都同时回到原处,就是求这些循环长度的最小公倍数。


网上很多都说了类似的一段话:

对于所有的环长 $L_i$ ,一定有 $\sum\limits_{i=1}^{n} L_i = n$。 —-网络

样例不就是 $3+3+3+2+2+1=14 \neq 6$ 吗?


好的,我太菜了,写完才反应过来,对于样例,有 (1,2,3)(4,5)(6) 这三组环。意思不是每个数的循环 qwq

emm,这样,问题就转化成:在 $n$ 的所有正整数拆分中,有多少个不相同的最小公倍数。

最小公倍数是可以转化为各个质因子的乘积的,这样,只要枚举质因子及其的幂,就一定可以枚举出不一样的最小公倍数。因为质因子可以取很多个,所以这就可以转换为完全背包问题。

先设一个二维的状态:$f[i][j]$ 表示前 $i$ 个质数的和为 $j$ 的情况数。

这样就可以很轻松的得出转移方程:

然后就可以倒一下循环的顺序就可以把二维降为一维,还有记得最后再循环一遍统计答案。

还有一点需要注意,对于 $n$ 的 “拆分”,其实 “拆分” 的各数之和小于 $n$ 也没有关系,因为可以用 1 补。

$Test’s$ $Code$:30% ($\frac{12}{1000}$ 的打表还有 30 分,数据太感动(shui)了)

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e3 + 5;

int n, a[MAXN];

int main() {
scanf ("%d", &n);
a[1] = 1;
a[2] = 2;
a[3] = 3;
a[4] = 4;
a[5] = 6;
a[6] = 6;
a[7] = 9;
a[8] = 11;
a[9] = 14;
a[10] = 16;
a[11] = 20;
a[12] = 23;
printf ("%d\n", a[n]);
return 0;
}

$Fixed$ $Code$:100%

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e3 + 5;

int n, p[MAXN], cnt;
long long f[MAXN], ans;
int main() {
scanf ("%d", &n);

p[++cnt] = 2;
for (int i = 3; i <= n; i += 2) {
int flag = true;
for (int j = 1; j <= cnt; j++) {
if (i % p[j] == 0) {
flag = false;
break;
}
}
if (flag) {
p[++cnt] = i;
}
}

f[0] = 1;
for (int i = 1; i <= cnt; i++) {
for (int j = n; j >= p[i]; j--) {
int temp = p[i];
while (temp <= j) {
f[j] += f[j - temp];
temp *= p[i];
}
}
}

for (int i = 0; i <= n; i++) {
ans += f[i];
}
printf ("%lld\n", ans);
return 0;
}

windy数

听 $dalao$ 们说都是数位 $dp$ 的模板题,但是数位 $dp$ 喔不会啊 qwq

似乎差不多就是把每位分开来模拟 $dp$。


总结

失败的一天,没有订完题。QAQ

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×