UOJ Round #9
A. 电路手动分析
30
$n, m \le 4$
$r \le 13$
选择一个子图使得补成团的边数不超过 $r$。
设其点数为 $n_v$ 边数为 $n_e$，应有 $\frac{n_v (n_v - 1)}{2} - n_e \le r$。
暴力枚举每个导出子图检查合法性。
时间复杂度 $\mathcal O(2^{n + 1m})$。
50
$n = 1, m \le 10^9$
显然应当选取连续的一段点，当点个数相同时在哪里选都是一样的，于是二分答案。
时间复杂度 $\mathcal O(\log m)$。
70
$n, m \le 1000$
仍然二分答案。
子图可能是不规则的，但是人类直觉告诉我们它一定是基于某个矩形扩展出的。
枚举矩形的边长检查答案。
时间复杂度 $\mathcal O(n m \log nm)$。
100
$n, m \le 10^9$
对于一个 $n_v$，其对应 $\frac{n_v (n_v - 1)}{2}$ 是一定的，为了答案尽可能成立，应当使 $n_e$ 尽可能大。
于是选择长宽尽可能相等的最大矩形。
令 $n \le m$。
设矩形边长为 $a = \min(n, \sqrt n_v), b = \lfloor \frac{n_v}{a} \rfloor$，不在矩形中的点个数为 $c = n_v - a \times b$。
此时矩形内部的边数为 $a(b - 1) + b(a - 1)$，矩形外部的边数为 $\max(0, c + (c - 1))$。
若有 $\frac{n_v (n_v - 1)}{2} - (a(b - 1) + b(a _ 1)) - \max(0, c + (c - 1)) \le r$，则 $n_v$ 是一个合法的答案。
时间复杂度 $\mathcal O(\log nm)$。
B. App 管理器
30
$n, m \le 17$
给定一张混合图，求一个给无向边定向的方案，使得定向后的图强连通。
暴力枚举每条无向边的方向检查答案。
时间复杂度 $\mathcal O(n 2^m)$。
70
所有 $t_i = 0$
一个强连通图的基图一定是边双连通图。
跑 DFS 生成树，把所有树边定为父亲到儿子的方向，把所有返祖边定为后代到祖先的方向，这样构造的图一定是强连通的。
时间复杂度 $\mathcal O(n + m)$。
100
$n, m \le 5000$
图一开始一定满足强连通性质。
考虑一条无向边 $u - v$。
- 如果从 $u$ 到 $v$ 存在一条不经过这条边的路径，那么我们可以把它定向成 $v \rightarrow u$；
- 如果从 $v$ 到 $u$ 存在一条不经过这条边的路径，那么我们可以把它定向成 $u \rightarrow v$。
两种情况必然会出现一种。
时间复杂度 $\mathcal O(m^2)$。
C. 包子晚宴
20
待在原地不动，全部输出 S。