2017-2018 ACM-ICPC, Asia Daejeon Regional Contest

Problem A

Upsolved by zerol.

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

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

Problem B

Solved by ultmaster. 02:47 (+)

Problem C

Solved by ultmaster. 00:31 (+)

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 (+)

Problem I

Solved by ultmaster. 03:27 (+)

Problem J

Unsolved. 01:19 (-2)

Problem K

Solved by zerol. 02:57 (+)

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

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

Problem L

Solved by kblack. 03:54 (+)

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

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