2018 KAIST RUN Spring Contest

Problem A

Upsolved by kblack.

题意：一个 $R \times C$ 的四消游戏，每次可以放一对相邻的珠子（上下或左右），需要在规定步数内造出指定图形。

题解：如果一列有偶数个，从下往上慢慢堆总是好的，奇数个的话，用三对珠子 $(2, 1)$, $(2, 2)$, $(2, 2)$ 就能解决多出的这一个。放的时候先处理所有奇数，然后无脑堆即可。

Problem B

Solved by ultmaster. 01:06 (+4)

题意：有一个字符串支持三种操作。

1. 在末尾添加一个字符。 2. 在末尾删除一个字符。 3. 询问字符串中的回文子串数目。

题解：数据范围不大，暴力就行。不知道为什么卡常。

Problem D

Solved by zerol. 01:45 (+)

模拟+打字 题。

Problem E

Upsolved by ultmaster. (-6)

题意：有 $n$ 个任务，第 $i$ 个任务最晚 $l_i$ 开始做，需要 $d_i$ 时间做完。问最多能做多少任务。

题解：这种贪心从来都不会做的，甚至还会搞出一堆错误的 DP、数据结构解法。

正解是这样的：按照 $(l_i + d_i, d_i)$ 排序。然后一个一个放进来，如果可以放当然最好，如果不能：那这个任务肯定放不进去了，但我们可以改善前面的决策：我们可以把前面的任务里耗时最长的一个替换成当前这个（如果替换能产生收益的话）。证明摸了。

zerol 的假算法不知道是不是做了另一个问题。

Problem G

Solved by kblack. 02:26 (+3)

其实好像就是一个最短路，统计稍微麻烦点，注意自环。

Problem H

Solved by zerol. 02:32 (+1)

题意：给一个 01 串。可以选择去掉连续的一段（也可以不去）并在该位置插入一个 1。求方案使得字典序最大。

题解：前面的 1 保留，然后保留剩下的后缀中字典序最大的。后缀中字典序最大的是用在 SAM 的转移边上跑，尽可能跑 1，跑到不能跑为止。

Problem I

Upsolved by ultmaster.

题意：求从 $1$ 到 $n$ 经过边数为 $k$ $(k \le 5)$ 的最短路径。

题解：大力讨论：

1. $k=1$，直接做。

2. $k=2$，枚举中间一个点，没什么好说的。

3. $k=3$，枚举中间的边。

4. $k=4$，枚举中间的点。然后我们需要枚举记录：从起点出发的所有 $(1,u,v)$ 记录在 $v$ 点上，到终点的所有 $(v,w,1)$ 记录在 $v$ 点上，对于每个 $v$ 选从起点出发、到终点的两个对暴力配对一下就好了。

5. $k=5$，与上一种情况类似，只不过最后计算的时候我们是枚举中间的边，比如这条边是 $(x,y)$，两条路径是 $(1,u,x)$，$(y,v,1)$，我们要满足 $u \ne x, x \ne y, x \ne v$，所以需要配 $3 \times 3$。注意不要与 $1$ 和 $n$ 重叠。

似乎非常容易写错。最后面向数据编程了艰难地过了。

Problem K

Solved by ultmaster. 00:17 (+2)

题意：签到。

题解：非要搞个炫酷的写法，结果 WA 了两发，背大锅。