第九届ACM山东省赛总结

简易题解：

A

题意就不说了，只考虑第一个字符串和第二个字符串的每种字母有多少个，然后贪心的考虑怎么变化，比如后面需求两个 A，那么先考虑依次前面有没有 Z 、Y、X 来转化。不过这题也可以写最小费用流，KM 二分图最佳完美匹配，毕竟只有 26 × 2 个点。

B

n × n 的棋盘，每个格子上有一个非负的值，0 表示不可选，其他值可选，需要选择若干个格子，并且所选的格子不能同行或同列，在保证选的格子尽量多的情况下使得选的权值最小的格子尽量的大。

如果只考虑让选的格子尽量的大的话，那么这就是一个二分图的模板题，假设棋盘最多选 M 个格子，这里选择的最小的格子尽量大，那么二分答案，考虑删除小于答案的格子剩下的格子能否选够 M 个。

据说出题人卡了网络流的写法…不知道匈牙利能不能过，我不放心复杂度写的 HK。

C

给出一个 N 个节点的无向图，初始没有边，让你连边使得图连通，节点编号 1 到 N，建一条 i 号节点到 j 号节点的边的花费是 (i + j)，那么显然答案就是从 1 开始对每个节点建 n - 1 条边。

D

给出一颗树，每条边有容量和权值，叶子可以走到根节点，然后路径上的权值和乘走的流量就是对答案的贡献，问答案的最大值。

考虑每个叶子到根的权值和，递减排序。依次选取权值和最大的叶子，让他尽可能的走。这样计算出来就是最大的答案，这个贪心很显然就能想到是正确的。

这里需要用到树链剖分维护一条链的信息，选取一个叶子的时候，首先看他到根节点这条链上容量的最小值为多少，然后让他走完这些流量，最后让这条链删去这些流量。

E

给出 1 到 N 的数的一个排列，一个 Good 数的定义为前面至少有一个小于他的数，要求删掉一个数，使得剩下的 Good 数尽量的多，多解输出最小解。

这里我用单调栈维护了，其实只需要维护最小值和次小值就可以了。

对于每个数，我们考虑删除他之后会少几个 Good 数，我们维护一个单调栈和出栈元素的最小值，到 i + 1 位置时，我们首先让栈里大于 i + 1 位置的数出栈，如果队列里的元素只有一个并且出栈的元素没有小于 i + 1 位置的，那么必须由栈里的这个来成为小于 i + 1 位置的数，删掉栈里这个数之后失去的 Good 数的数量加一，然后 i + 1 位置的数入栈。

最后删掉最没有贡献的数就可以了，并考虑这个数是不是 Good 数。

F

容斥定理，考虑区间之间交的情况，首先加上全部区间长度相乘，然后减去第一个和第二个相等，第二个和第三个相等…然后加上第一个和第二个并且第三个相等…

可以手写一下，对拍验证…最后我也不知道有没有写对

G

A 和 B 进行 Nim 博弈，B 开局可以移除至多 D 堆，问 B 有多少种移除堆的方案能过胜利。

这里数据范围很小，至多 1000 堆，每堆大小至多 1000，D 至多 10 堆。

显然如果 B 要赢必须要保证所有堆的异或和为 0 。

依次从左到右考虑每堆选不选，设 $dp[i][j][k]$ 的值为考虑完第 i 堆，前 i 堆的异或和为 j，移了 D 堆的方案数。

那么 $\sum_{i=0}^ddp[n][0][i]$就是最终答案，转移如下

$dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j \oplus h_{i-1}][d-1]$

如果 k 等于 0 的话仅考虑 $dp[i - 1][j][k] $ 的转移。

热身赛：

当时榜炸掉了…然后完全没有跟榜，做题是按难度递减做的，先写了一发最难的 A 题，正解是区间 DP，然后以为是签到题，写了个假算法就交上去了。然后看了下 B 题是训练赛的原题，二维偏序或者主席树、线段树合并都可以写，于是上去就写了，然后拿了 A 区的第一个 B 题的气球（毒瘤开题）。然后做的 C，大概是我出的大一上学期期末考试题的变式 ？D 题我没看，队友说可以写就写完 A 了，应该是一个特别水的签到题。

最后 A 题也是完全没思路，我完全没往区间 DP 上想，其实这个热身赛的榜的前几名已经和正式赛的榜差不多了…

然后发现山大和中石油的强队有点多，起初我们还是以为山大和中石油只有一两个比我们强的，运气好还能捧个杯？（雾）结果比我们强和实力相当的大概有六七个，就有点绝望了，不过还好实力差距还不是很大。

正式赛：

首先先看的 C，标准的签到题，让队友敲的，结果 WA 了两次才 A，可以说是开局非常爆炸了，于是导致我后面交题也不怎么看罚时了（不知道算不算什么破釜沉舟背水一战），想着只能靠题数取胜了。

然后看的 B，理解错了题意，正确的题意是符合贪心性质的，可以写贪心，我大概是做了个 Hard Version，写了个最小费用流，非常熟练的抄完自己总结的板子，保存边的数量的变量没初始化 RE 了一发，然后由于不考虑罚时，于是改完就立刻交了一发就 A 了。

在我写 B 的时候队友就已经在看 F 题了（数据出错的那个题），等我写完他告诉了我一下容斥的做法，我觉得没什么问题就开始敲了，不过写的过程中感觉非常难写…看到榜单上 6 分钟就 AC 的，怀疑自己的做法是不是不对…然后让队友写了个对拍自己去重新想了一下思路，发现还是得写容斥，于是回来继续写，写完后又对拍了几组数据改了改就交了，然后肯定是 A 的，最后也不知道这个题有没有写对 ORZ

这时候另一个队友一直在读题，我敲完一道题基本上就可以接着看下一道题了，这时候一个队友在想 E 题，我去写 G 题，然后一眼看过去就是 NIM 博弈加 DP 记录方案数，不过这里数据越界改了好几次才过，不过改完一次就交一次不在乎罚时，所幸改的还算快。

在我改 G 题的时候让队友敲了下 E 题，NlogN 的复杂度 TLE 了，感觉必须得线性的算法才能过，这时候封榜还有半个小时，榜上已经有六题的了，于是决定让队友去其他的题了（B 和 D），然后我考虑这个题的答案限制条件比较少，应该用不到队友敲得逆序数之类的，于是正好我们都想到单调队列，于是先写了个单调队列，然后测了下样例对了，要交的时候还是不放心，因为如果这个 WA 的话我不能确定是算法错了还是代码细节错了，于是让队友出了下样例果然错了，后来多考虑了一个条件就 OK 了，然后提交 AC。

这时候队友说 B 题有思路了，不过是图论题还是让我敲，我一直感觉 1e8 的时间复杂度过不去，于是先让队友把板子抄上，然后自己想了下细节怎么处理，感觉没问题之后就开始上手做了，写完 debug 了 20 多分钟，队友板子抄错了两个地方，改完过了另一个队友出的特别强的样例（反转他说是比较强），提交就 AC 了。

这时候比赛结束还有四十分钟，榜上已经有七题的队伍了，加上我们罚时比较高，夺冠要在这 40 分钟 A 两题感觉希望不太大了，有点失望…队友在我写 B 题的时候已经想了下大概的 D 题做法，我问了他一下，感觉加上树链剖分就可以写了，于是拿过来之前直接整理的树链剖分板子就超了起来，心情比较差加上又特别累了，中间电脑还重启耽误了十多分钟，最后还有十分钟结束才写完，总共 200 多行代码，我当时就和队友说，这么长的代码要是不出点 Bug 什么的我都不信，结果运行没编译错误，然后输入样例结果却都是 0 … 非常紧急的改完之后还剩五分钟了，最终居然过了样例，当时 PC ^ 2 显示结束还有三分钟立刻就交了，之后就赶紧看代码还有没有错误。然后看着看着队友说有评测结果了，看了一下返回了一个 Yes，可以说是非常开心了。

总结：

这场比赛打起来还算是非常开心的，F 题出错了也没有耽误我们太长的时间，题目基本上都是看到了就有大概的思路和做法了，只有 E 和 F 想的时间长一点。整体发挥还算是不错，不过细节失误算是比较多，比如没初始化，数组越界，感觉就是 200 行代码居然没有细节错误，但是写的非常短很有自信的代码错了两三处，感觉非常奇怪…