2017-2018 ACM-ICPC, Asia Daejeon Regional Contest

Problem A

Upsolved by zerol.

题意：造一些可以指定半径的广播站（半径至少为 1），使得树上的所有结点都被至少一个广播站覆盖。

题解：树形 dp。以下省略 100 字。

Problem B

Solved by ultmaster. 02:47 (+)

题意：有一种奇怪的游戏，求最后满足某种状态的某人获胜的局面数。

题解：看起来是博弈但不是博弈，看起来是 DP 但不是 DP，其实就是个 SB 搜索。（垃圾选手常年不写代码已经不会搜索了... 甚至还要依赖队友调一个 DFS...）

跑了还有点久（0.7 秒），最后打了个表交了上去。

Problem C

Solved by ultmaster. 00:31 (+)

题意：只能从度数小的点走到度数大的点，求最长路径。

题解：转化成一个 DAG，然后（天然）拓补排序之后 DP 一下就可以。（记忆化搜索其实更好些... 不过某垃圾选手已经常年不写代码了... ）

Problem D

Solved by zerol. 00:15 (+)

签到题。

Problem E

Solved by kblack. 01:24 (+)

题意：给出一个带权无向图，问使得每条边分别可以出现在最小生成树上各自需要删除的边数之和。

题解：需要删除的边数，等于所有权值更小的边不能将两个点联通，求 $m$ 遍最小割即可，$2.5 \times 10^{9}$ 竟然跑得贼快。

Problem F

Solved by kblack. 00:40 (+1)

题意：给出 $k$ 阶希尔伯特曲线，求长度对应的坐标。

题解：确定再哪个子图，递归后对坐标变化即可。推完公式抄错，唯一断签QAQQQ。

Problem G

Solved by kblack. 02:43 (+)

题意：给出两个阶梯型折线，求第二条再第一条上，且封闭的部分的面积。

题解：题目很友好，所有的下标都是唯一的，扫一遍即可，区域数等于互相穿过的次数的一半，注意左右的开放区域不计入。

Problem H

Solved by ultmaster. 01:01 (+)

题意：给两个石头剪刀布的序列，求最好的匹配位置使得你赢的次数尽量多。

题解：分三种匹配情况跑三次 FFT（等于字符串匹配，校赛原题）。虽然听上去很假，但 rush 了一下就过了。很舒服。

Problem I

Solved by ultmaster. 03:27 (+)

题意：给一个瞎跑一段然后转圈圈的数列，求最小的瞎跑距离和循环周期。

题解：二分 $k+p$，然后用剩下的那段在原串里做 KMP，求最后一个合法（不超过 $k$）的匹配位置就可以得到最小的 $p$。

赛后看到一种解法说只要对反串做 KMP 就可以拿到每一个点的 $p$ 了。觉得很妙。

Problem J

Unsolved. 04:58 (-2)

随机算法冲了两发没过去。

Problem K

Solved by zerol. 02:57 (+)

题意：给定平面上折线的行进方向和距离，要求修改距离使得不自相交。

题解：层层向外扩展。保证每一次行进的终点在之前围成的矩形区域之外就好了。

Problem L

Solved by kblack. 03:54 (+)

题意：一群人要各自在自己的图里跑，留在原地和到临点都有代价，求所有人同时在各自终点的最小代价。

题解：时间最多会到 $O(N^3)$，枚举时间跑最短路，最后合并即可。