UOJ Round #7
A. 水题生成器
30
$n \le 5$
$5! = 120$，只有 $16$ 个约数，可以 $16^5$ 枚举子集。
时间复杂度 $\mathcal O(d(n!)^n)$。
70
$n \le 9$
可以看成背包问题。
有 $d(n!)$ 个体积为 $1$ 的物品，背包容量为 $n$，求总价值为 $m$ 的方案。
时间复杂度 $\mathcal O(d(n!) m)$。
100
$n \le 20$
求出 $n!$ 的所有约数（$n = 20$ 时有 $41040$ 个），从大到小尝试减去，一定能够在 $n$ 次内减到零。
注意找约数时 $\mathcal O(\sqrt{n!})$ 不如 $\mathcal O(2^n)$。
B. 水题出题人
5
归并排序 merge_sort 计数排序 counting_sort
计数排序的用时与序列的最大元素有关，只需令 $n = 1, a_1 = 2333333$ 就可以了。
13
冒泡排序 bubble_sort
选择排序 selection_sort
在升序排列中某个位置放一个正无穷，二分序列长度及其位置。
31
归并排序 merge_sort
快速排序 quick_sort
根据快速排序的原理，每次将序列中心设为最大值。
C. 水题走四方
20
$n \le 12$
记录当前两个地卜师在什么位置并用状态压缩表示每个结点是否被访问过。
时间复杂度 $\mathcal O(n^3 2^n)$。
50
$n \le 100$
有两个地卜师，一个是本体一个是分身，在树上乱逛。
如果两个地卜师站在一起是分不清楚也不用分清楚谁是谁的，可以根据需要调换两人的身份。
所以对于任意一组移动方案一定可以把这组方案调整成本体从来没有瞬移过的方案。
本体一定是往下走几步，停几步，再走几步，再停几步，如果一组方案最后本体没有停在某个叶子，肯定可以让本体追随分身的脚步停在某个叶子。
现在本体是从根走到了某个叶子 $v$，现在考虑其它还没有被访问的结点。
我们称根到 $v$ 的链为主链，那么要让分身来访问主链上支出去的那些子树。
可以断言一组最优方案一定是这样的：主链上有一些关键结点，分身和本体本来一起走，走到关键结点处分身会下去访问这个关键点到下一个关键点之间所有支出去的子树的叶子，访问一个，瞬移回来，当还剩下一个叶子的时候本体和分身一起往下，本体去下一个关键点，分身去叶子，分身到了叶子处就瞬移到本体所在位置。
对于“最后一个访问的叶子”，显然取最深的叶子最优。
使用 DP 求出 $f[v]$ 为从根到关键点 $v$ 时的最短时间，然后在每个叶子的 $f$ 中取最小值就可以了。
假设已经知道是哪条主链，设 $d[v]$ 为结点 $v$ 的深度，$d_m[v]$ 为主链上结点 $v$ 往外伸出去的子树中最深的叶子的深度，$d_m[u, v]$ 为主链上结点 $u$ 到结点 $v$（不包括结点 $v$）往外伸出去的子树中最深的叶子的深度，$d_s[v]$ 为结点 $v$ 的子树中叶子的深度之和，$n_l[v]$ 为结点 $v$ 的子树中叶子的个数。
\[f[v] = \min_u \\{ f[u] + d_s[u] - d_s[v] - (n_l[u] - n_l[v]) \cdot d[u] + \min \\{d[v] - d_m[u, v], 0 \\} \\}\]其中 $u$ 是 $v$ 的祖先。
一边 DFS 一边 DP，时间复杂度 $\mathcal O(n^2)$。