2015-2016 Makoto rng 58 Soejima Сontest 4

Problem B

Unsolved. (-2)

题意：求一个最大的 $D$，使得在只有大于等于 $D$ 的点才能连通的情况下整个图连通。

假算法：就是在某一个点上盖一个菱形的罩子把所有点罩住，并且罩子要最小。转化成对每一个点求出曼哈顿距离最远的点。迅速写完。WA19。

Hack 数据：(0,0),(1,0),(0,1),(1,1)

真算法：找到最远的点跟最远的点相连建图，跑最大生成树。

Problem C

Unsolved.

题意：存在某些撑杆跳的位置，把坐标 $x$ 变成 $2 a_i - x$。求最小步数从 $s$ 到 $t$。

题解：听起来像是非常标准的 DP。但不知道因为什么原因感觉复杂度不够，所以没做（去投资 B 去了）。

Problem E

Solved by ultmaster. 00:07 (+)

签到。

Problem F

Solved by kblack. 04:13 (+3)

没有打破每次都能过 F 的铁律。

Problem I

Solved by kblack. 01:49 (+)

题意：一堆机器人，互相碰到就会开始向一个方向行走，问 T 时刻机器人位置（也就是被启动的时间）。

题解：记录每个机器人的位置4个方向出现机器人的最短时间，扔进堆里松弛即可。

Problem H

Unsovled.

Problem J

Solved by kblack. 00:24 (+)

题意：规定一些点的度数，求生成树计数。

题解：purfer 序列裸题。

Problem K

Solved by ultmaster. 00:38 (+2)

题意：每次操作可以在一个字母后面加一个跟这个字母不一样的字母。问 $s$ 能否通过若干次操作变成 $t$。

题解：听起来像是标准的 DP。有个小问题就是 a 可以变成 abbaaa。也就是说只有后面一个紧跟着的字母不相等，后面所有的状态都推的出来。