2015-2016 Makoto rng 58 Soejima Сontest 4

Problem A

Upsolved by ultmaster.

2018 Multi-University, HDU Day 4 的 A 的一个温暖版。

Problem B

Upsolved by zerol. (-2)

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

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

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

真算法：二分答案，对点按 x+y 以及 x-y 排序，每个点只需判断与最大的和最小的点是否能够连边，判连通性。

Problem C

Upsolved by ultmaster.

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

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

Upsolve: 移项以后以后发现可以产生两种形式：

$\sum_{j=1}^k(-1)^{j-1}\cdot a_{i_j}=\begin{cases} \frac{1}{2}(s-t), &k \text{ is even}\\ \frac{1}{2}(s+t),&k \text{ is odd} \end{cases}$

分奇偶两种情况 BFS 即可。注意到由于一正一负，总是可以调整顺序使得不会跳飞掉。（真的吗？）上限开到 2E5 也足已通过。

Problem E

Solved by ultmaster. 00:07 (+)

签到。

Problem F

Solved by kblack. 04:13 (+3)

题意：对于一个给定的 $M$，可以把数轴分成 $[1,M],[M+1,2M],[2M+1,3M],\ldots$ 这样的切片。已知切片满足条件：任意一个区间都被完全包含在一个切片内；任意两个区间都属于不同的切片。问有多少个可能的 $M$。

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

$M$ 小的时候暴力 check，$M$ 大的时候检查区间合法性。具体细节留给 kblack 补充。

Problem I

Solved by kblack. 01:49 (+)

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

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

Problem H

Unsovled.

Problem J

Solved by kblack. 00:24 (+)

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

题解：Prufer 序列裸题。

Problem K

Solved by ultmaster. 00:38 (+2)

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

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