2015-2016 Makoto rng 58 Soejima Сontest 4

From EOJ Wiki
Jump to: navigation, search

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。也就是说只有后面一个紧跟着的字母不相等,后面所有的状态都推的出来。