UOJ Round #11
A. 元旦老人与汉诺塔
30
$n \le 50$
$m \le 10$
每个状态下能进行的操作最多有 $3$ 种，暴力枚举每一步的选择判断是否与目标状态相同。
时间复杂度 $\mathcal O(3^m n)$。
50
$n \le 10$
$m \le 50$
汉诺塔的合法状态只有 $3^n$ 种，开一个数组 DP，状态包含当前步数及状态。
时间复杂度 $\mathcal O(3^n m)$。
100
$n \le 100$
$m \le 100$
使用记忆化搜索。
B. 元旦老人与丛林
20
$n \le 10$
$m \le 20$
暴力枚举边集判定。
时间复杂度 $\mathcal O(2^m m)$。
40
$n \le 300$
$m \le n + 7$
保证图连通
在一棵树上加了很少的边，考虑把无用的点和边删掉。
可以发现度数小于等于 $2$ 的点是否存在是没有影响的，于是每次找一个度数小于等于 $2$ 的节点删掉，最后剩下边数很少，直接暴力枚举。
50
每个点的度数都不小于 $4$
每一个点的度数都不小于 $4$，所以可以得到 $m \ge 2n$，显然无解，输出 No。
80
$n \le 300$
$m \le 600$
如果图的每一个非空子图都满足 $\lvert E \rvert \le 2 \lvert V \rvert - 2$，那么它一定是丛林。
问题转化成判断当前的图是否存在一张非空子图满足 $\lvert E \rvert \gt 2 \lvert V \rvert - 2$，这个问题又可以转化成最大权非空闭合子图。
新建一张 $n + m$ 个点的图，其中前 $n$ 个点的权值是 $- 2$，后 $m$ 个点的权值是 $1$，如果在原图中第 $i$ 条边连接的点是 $u_i$ 和 $v_i$，那么就分别连上 $i + n$ 到 $u_i$ 和 $v_i$ 的边，只需判断新图的最大权非空闭合子图的权值是否大于 $- 2$。
直接做是不行的，因为当最大权非空闭合子图的权值小于 $0$ 时，最大权闭合子图的权值就是 0。
我们可以强制选取某一个点，即把某一个点的权值设为 $0$，如果存在一个包含这个点的子图满足 $\lvert E \rvert \gt 2 \lvert V \rvert - 2$，那么这个子图的权值就变得大于 $0$ 了。
枚举这个点，跑 $n$ 次网络流，时间复杂度 $\mathcal O(n m \sqrt n)$。
100
$n \le 2000$
$m \le 4000$
相邻两次最大流之间只有两条流量为 $2$ 的边发生变化，所以直接用退流搞。
时间复杂度 $\mathcal O(\sqrt{n} m + n m)$。
C. 元旦老人与数列
10
$n \le 3000$
$m \le 3000$
暴力模拟。
时间复杂度 $\mathcal O(n m)$。
30
不存在操作二
历史最值问题。
线段树上打永久标记即可。