Part 1 题解

A 「MZOI2020」快速班号变换

给定一个人的班号,现在你有三种变换方式:

  1. 将一位上的数字替换成另一个数字,花费为这两个数字的李距离.
  2. 插入一个数字,花费为插入的数字.
  3. 删除一个数字,花费为删除的数字.

在十进制中,数字 $a$ 和 $b$ 的李距离为 $\min{|a−b|,10−|a−b|}$.

现另指定一个班号,求这个人的班号变换到指定班号的最小花费.

数据范围 $10^{1000}$

非常显然的一个 DP,没有做出来的人都写在题目背景里了。

设 $f[i][j]$ 表示 $a$ 的第 $i$ 位以前和 $b$ 的第 $j$ 位以前都匹配好了的最小花费,分类讨论一下就可以转移了。

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
#include<bits/stdc++.h>
using namespace std;

int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

const int N = 1005;
char a[1005], b[1005];
int f[N][N], n, m, suf[N];
// f: a 的第 i 位以前所有数和 b 的第 j 位以前完成匹配的最小代价

int dist(int x, int y) {
return min(abs(x - y), 10 - abs(x - y));
}

int main() {
scanf("%s", a + 1); scanf("%s", b + 1);
n = strlen(a + 1), m = strlen(b + 1);
memset(f, 0x3f, sizeof(f));
f[1][1] = 0;
for(int i = n; i > 0; i--) suf[i] = suf[i + 1] + a[i] - '0';
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(f[i][j] == 0x3f3f3f3f) continue;
f[i + 1][j] = min(f[i + 1][j], f[i][j] + a[i] - '0'); // 删除一位
f[i][j + 1] = min(f[i][j + 1], f[i][j] + b[j] - '0'); // 在这一位前面插入 b[j]
f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j] + dist(a[i] - '0', b[j] - '0')); // 修改
}
}
int ans = 0x3f3f3f3f;
for(int i = 1; i <= n + 1; i++) ans = min(ans, f[i][m + 1] + suf[i]);
printf("%d\n", ans);
return 0;
}

B 「MZOI2020」魔导书

有 $n$ 本书,每本书有一个满意度 $a_i$ 和一个承重量 $b_i$,在这些书里选出若干本堆起来,求最大的满意度。

先按 $b_i$ 从大到小排序,然后从下往上贪心。

书堆最多能放 $n$ 本书,从 $n\rightarrow1$ 枚举每一个位置,$b_i$ 如果大于等于当前位置那么一定放在这里是没问题的,就把所有满足这个条件的 $b_i$ 加进一个优先队列,贪心选最大值。

注意开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
#include<bits/stdc++.h>
#define int long long
using namespace std;

int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

const int N = 1e6 + 5;
int n, a[N], b[N];
priority_queue<pair<int, int> > q;
priority_queue<int> p;

signed main() {
n = get();
for(int i = 1; i <= n; i++) a[i] = get();
for(int i = 1; i <= n; i++) b[i] = get(), q.push(make_pair(b[i], a[i]));
int ans = 0;
for(int i = n - 1; i >= 0; i--) {
while(q.size() && q.top().first >= i) p.push(q.top().second), q.pop();
if(p.size()) ans += p.top(), p.pop();
}
printf("%lld\n", ans % 910666);
return 0;
}

C 「MZOI2020」遗传因子

给出 $n$ 个遗传因子 $s_i$, 均由小写字母组成.

对于遗传因子 $s_i,s_j$, 有任意字符串 $p,q$ 使得 $p+s_i+q=s_j$, 其中 $p$, $q$ 可以为空字符, 加号为字符串拼接, 那么称 $s_j$ 发生了 $|p|+|q|$ 次分离.

你需要求得每个遗传因子分离的次数.

考虑 AC 自动机的性质。

  • Trie 树上某一个点到根的路径上的每一个点都是它的前缀
  • Fail 树上某一个点到根的路径上的每一个点都是它的后缀
  • 前缀的后缀就是子串

于是我们统计 Fail 树上每个节点到根的路径(不含本身)上的 End 节点个数、End 的长度之和,然后在统计 Trie 树上上述信息的前缀和(也不含本身),然后有 $\sum|p|+|q|=CntEnd\times |s_j|-SumEnd$

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
#include<bits/stdc++.h>
using namespace std;

int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

const int N = 1e6 + 5;
int n, tot;
char s[N];
int ch[N][26], len[N], End[N], sum[N], shit[N], fail[N], fa[N];
int psum[N], pEnd[N], ans[N];

int insert(char S[], int len) {
int u = 0;
for(int i = 0; i < len; i++) {
if(!ch[u][S[i] - 'a']) ch[u][S[i] - 'a'] = ++tot;
u = ch[u][S[i] - 'a'];
}
End[u] = 1, sum[u] = len;
}

void bfs() {
queue<int> q;
for(int i = 0; i < 26; i++) if(ch[0][i]) fail[ch[0][i]] = 0, q.push(ch[0][i]);
while(q.size()) {
int u = q.front(); q.pop();
psum[u] = psum[fail[u]] + sum[fail[u]], pEnd[u] = pEnd[fail[u]] + End[fail[u]];
for(int i = 0; i < 26; i++)
if(ch[u][i]) {
fa[ch[u][i]] = u;
fail[ch[u][i]] = ch[fail[u]][i];
q.push(ch[u][i]);
}
else ch[u][i] = ch[fail[u]][i];
}
}

int main() {
n = get();
for(int i = 1; i <= n; i++) {
scanf("%s", s);
len[i] = strlen(s);
shit[i] = insert(s, len[i]);
}
bfs();
for(int i = 1; i <= tot; i++) psum[i] += psum[fa[i]] + sum[fa[i]], pEnd[i] += pEnd[fa[i]] + End[fa[i]];
for(int i = 1; i <= n; i++) {
ans[0] += (ans[i] = len[i] * pEnd[shit[i]] - psum[shit[i]]);
}
for(int i = 0; i <= n; i++) printf("%d\n", ans[i]);
return 0;
}

我竟然拿到了最快 & 最短代码!

Part 2 总结

我从这次考试中学到的东西:

  • 不要看啥都是 DP(比如今天 T2),贪心也是很重要的东西。重点是证明可以贪心。
  • 记住某些算法的性质,比如 AC 自动机,Trie 树和 Fail 树。
  • 果然橙队还是太强了

关于 T3 为什么只有 10 pts:我最开始写的暴力是先把串按长度排序,从 2 开始循环,然后可以卡卡常(其实貌似并不能),后来发现输出顺序不对就不排序了。于是从 2 开始循环就忘了改了……

$60\rightarrow 10$

所以一定要注意检查