2018 KAIST RUN Spring Contest

From EOJ Wiki
Jump to: navigation, search

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 C

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 F

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 J

Problem K

Solved by ultmaster. 00:17 (+2)

题意:签到。

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