Difference between revisions of "2015-2016 Makoto rng 58 Soejima Сontest 4"
m (→Problem J) |
|||
(5 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
+ | === Problem A === | ||
+ | |||
+ | Upsolved by ultmaster. | ||
+ | |||
+ | [[2018 Multi-University, HDU Day 4]] 的 A 的一个温暖版。 | ||
+ | |||
=== Problem B === | === Problem B === | ||
− | + | Upsolved by zerol. (-2) | |
题意:求一个最大的 $D$,使得在只有大于等于 $D$ 的点才能连通的情况下整个图连通。 | 题意:求一个最大的 $D$,使得在只有大于等于 $D$ 的点才能连通的情况下整个图连通。 | ||
Line 9: | Line 15: | ||
Hack 数据:(0,0),(1,0),(0,1),(1,1) | Hack 数据:(0,0),(1,0),(0,1),(1,1) | ||
− | + | 真算法:二分答案,对点按 x+y 以及 x-y 排序,每个点只需判断与最大的和最小的点是否能够连边,判连通性。 | |
=== Problem C === | === Problem C === | ||
− | + | Upsolved by ultmaster. | |
题意:存在某些撑杆跳的位置,把坐标 $x$ 变成 $2 a_i - x$。求最小步数从 $s$ 到 $t$。 | 题意:存在某些撑杆跳的位置,把坐标 $x$ 变成 $2 a_i - x$。求最小步数从 $s$ 到 $t$。 | ||
题解:听起来像是非常标准的 DP。但不知道因为什么原因感觉复杂度不够,所以没做(去投资 B 去了)。 | 题解:听起来像是非常标准的 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 === | === Problem E === | ||
Line 29: | Line 44: | ||
Solved by kblack. 04:13 (+3) | Solved by kblack. 04:13 (+3) | ||
− | + | 题意:对于一个给定的 $M$,可以把数轴分成 $[1,M],[M+1,2M],[2M+1,3M],\ldots$ 这样的切片。已知切片满足条件:任意一个区间都被完全包含在一个切片内;任意两个区间都属于不同的切片。问有多少个可能的 $M$。 | |
+ | |||
+ | 题解:没有打破每次都能过 F 的铁律。 | ||
+ | |||
+ | $M$ 小的时候暴力 check,$M$ 大的时候检查区间合法性。具体细节留给 kblack 补充。 | ||
=== Problem I === | === Problem I === | ||
Line 46: | Line 65: | ||
Solved by kblack. 00:24 (+) | Solved by kblack. 00:24 (+) | ||
+ | |||
+ | 题意:规定一些点的度数,求生成树计数。 | ||
+ | |||
+ | 题解:Prufer 序列裸题。 | ||
=== Problem K === | === Problem K === |
Latest revision as of 15:48, 23 August 2018
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。也就是说只有后面一个紧跟着的字母不相等,后面所有的状态都推的出来。