2017-2018 ACM-ICPC, Asia Daejeon Regional Contest
ECNU Foreigners
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)$，枚举时间跑最短路，最后合并即可。
One,Two,Three,AK
Problem A
题意：在一棵树上，选择一些节点造任意半径的广播站（半径至少为 1），使得树上的所有结点都被至少一个广播站覆盖。
题解：树形 dp。$dp[i][j]$表示在节点i构成的子树，至少要向上覆盖j层的代价。$dep[i][d]$表示i的子树上与i距离d层的那些点都被它们自己的子树覆盖到了的代价之和。 那么$dp[i][j]$，要么在i自己上建一个半径为j的广播站，要么在其相邻的子节点中选择一个节点，使得它的子树至少向上覆盖j+1层，其他的子树只要满足向下第j层满足子树覆盖。
Problem B
Solved by oxx1108 && Xiejiadong. 03:04:19(+)
题意：给出初始位置和最后的位置，求合法的方案数。
题解：暴力+记忆化直接就过了，时间复杂度$O(3^n)$。
Xiejiadong: dfs 都写丑了。背锅。
Problem C
Solved by oxx1108. 01:27:32(+2)
题意：只能从度数小的点走到度数大的点，求最长路径。
题解：转化成一个 DAG，然后拓扑排序之后 DP 一下就可以。看错结点下标卡了好久，初值也赋错导致卡了好久。
Problem D
Solved by oxx1108. 00:15:13(+2)
签到题。
Problem E
Solved by Xiejiadong. 04:44:16(+)
题意：$h[i]$表示最小需要删掉几条边，可以使得$i$边在最小生成树上，求$\sum h[i]$。
题解：显然，会对$i$边产生影响的，一定是权值比他小的边，把所有权值比他小的边拿出来，作为新的图，然后求最小割，就是$h[i]$。
Problem F
Solved by Xiejiadong. 01:11:10(+)
题意：给出路径递归生成方式，求第$x$步的位置。
题解：按照题意递归，注意第一部分和第四部分的旋转以后，起点和终点互换了。
Problem G
Upsolved by Xiejiadong.
题意：给出两条折线U和L，求U在上时的封闭面积。
题解：在$y$发生变化的$x$上打一个标记，因为$x$比$50000$小，直接扫一遍，算一下就可以了。
有一个特殊情况是样例3，可能$y$的变化会在$x=0$的时候发生。
Problem H
Solved by oxx1108. 02:02:32(+5)
题意：给两个石头剪刀布的序列，求最好的匹配位置使得你赢的次数尽量多。
题解：分三种匹配情况跑三次 FFT（等于字符串匹配，校赛原题），然后求和最大，bitset被卡了。
Problem I
Upsolved by Xiejiadong.(-6)
题意：给出一个字符串，去掉某一部分前缀以后，一定是一个循环字符串。
题解：kmp的next数组的应用。
反串构造next数组，那么对于反串的前$i$为，他的最小循环节长度一定是$i-next[i]$，这个就是$p$，那么$k=n-i+1$，这里直接美枚举所有$k$和$p$去$k+p$的最小值即可。
还要注意$k=0$的情况，所以枚举的时候要向后多找一位。
Problem J
Unsolved.
Problem K
Solved by Xiejiadong. 03:31:05(+1)
题意：给定平面上折线的行进方向和距离，要求修改距离使得不自相交。
题解：水平的和垂直的分开考虑，水平的如果和上一次的方向相同，走一步，否则走$i$步，可以有效避免冲突。垂直的处理方式类似。
Problem L
Upsolved by dream_cloud
题意：一群人不超过三个要各自在自己的图里跑，留在原地和到临点都有代价，求所有人同时在各自终点的最小代价。
题解：时间最多会到 O(N3)，枚举时间跑最短路，最后合并即可。跑最短路，一开始选择了dijkstra，但是tle了。由于边比较少，所以应该枚举边，去更新下一个时间，到各个节点的代价。