LibreOJ β Round #3
T1. 绯色 IOI（开端）
10
$n \le 10$
暴力枚举所有环状回路，时间复杂度 $\mathcal O(n! n)$。
使用回溯法在枚举时计算答案，并且只考虑 $1$ 为起点的回路，时间复杂度 $\mathcal O((n - 1)!)$。
30
$n \le 20$
记 $f_{S, i}$ 表示从点 $1$ 出发且经过 $S$ 中每个结点恰好一次最后到点 $i$ 的路径长度最小值，其中 $i \in S$。
\[f_{S, i} = \min_j \\{ f_{S - \\{ i \\}, j} + (w_i - w_j)^2 \\}\]答案为 $f_{V, 1}$。
时间复杂度 $\mathcal O(2^n n^2)$，空间复杂度 $\mathcal O(2^n n)$。
100
$n \le 100000$
发扬人类直觉，按照点权排序。
考虑每次走相邻的点，但是这样 $n \rightarrow 1$ 的边权会很大，那么每次隔一个点走，跳过的点留给反方向。
形式化地，连边 $(1, 2), (n - 1, n)$ 以及所有边 $(i, i + 2)$（$i = 1, 2, \cdots, n - 2$），构成的回路即为最优解。
时间复杂度 $\mathcal O(n \log n)$，空间复杂度 $\mathcal O(n)$。
T2. 绯色 IOI（抵达）
15
$n \le 10$
暴力枚举所有排列，求出每个城市的庇护所判断是否合法。
时间复杂度 $\mathcal O(n! n)$。
45
$n \le 2000$
设 $i$ 的庇护所为 $p_i$，则 $p_i$ 中所有环长为 $2$，即 $i$ 和 $p_i$ 构成完美匹配。
使用网络流或匈牙利算法求出完美匹配，转化为拓扑排序问题，将每个城市的庇护所向与它连边的非庇护所的城市连一条有向边。
时间复杂度 $\mathcal O(n^2)$。
55
每条道路满足 $v - u = 1$
- 当 $n$ 为奇数时，不存在合法解。
- 当 $n$ 为偶数时，前面一部分为连续上升的奇数，后面一部分为连续下降的偶数。
时间复杂度 $\mathcal O(n)$。
100
$n \le 5 \times 10^5$
借助树的特殊可以使用树形 DP 等算法在线性时间内求出其完美匹配，然后使用优先队列维护拓扑排序。
时间复杂度 $\mathcal O(n \log n)$。
T3. 绯色 IOI（危机）
20
$n \le 300$
性质一说明这是个 DAG，求和式表明答案只与相邻两项有关，于是 DP。
记 $f_i$ 表示以 $i$ 结尾的最大安全程度。
\[f_i = \mathop{\max} \limits_{j 能直接或间接引爆 i} f_j + F(v_j, v_i)\]注意间接也是要算的，于是先建出 DAG 然后求传递闭包。
时间复杂度 $\mathcal O(N^3)$。
30
$n \le 3000$
使用 std::bitset 优化传递闭包。
时间复杂度 $\mathcal O(n^2 + \frac{n m}{w})$。
40
$v_i = 1$
$v_i = 1$，那么 $F(1, 1) = 1$，问题转化成求以每个点结尾的最长链长，使用线段树维护区间最值。
时间复杂度 $\mathcal O(n \log n)$。
55
$v_i \in \{ 0, 1 \}$
$v_i \in \{ 0, 1 \}$，只有 $F(0, 0) = 1$ 其余都是 $1$，使用两棵线段树分别维护 $v = 0$ 和 $v = 1$ 的点的区间最值，转移时分类讨论。
时间复杂度 $\mathcal O(n \log n)$。
T4. 绯色 IOI（悬念）
34
$n \le 100$
$q \le 100$
暴力 $\mathcal O(n^2)$ 建图，每次修改后重新求匹配。
可以证明边数是 $\mathcal O(n)$ 级别。
时间复杂度 $\mathcal O(q n^3)$。