UOJ Round #12
A. 实验室外的攻防战
24
$n \le 8$
建立 $n!$ 个点表示所有可能的排列，对于每个点枚举交换哪两个元素，建出转移边进行 BFS 判断 $A$ 状态是否能到达 $B$ 状态。
56
$n \le 1000$
使用冒泡排序进行模拟，交换时判断一下。
如果经过 $n$ 轮之后仍然不能排成 $B$ 的样子就输出 NO。
为什么这样是对的呢？因为自信！
100
$n \le 100000$
假设 $A_{a_i} = i, B_{b_i} = i$，一个显然的结论是如果不存在 $1 \le i \lt j \leq n$ 满足 $a_i \lt a_j$ 且 $b_i \gt b_j$，则答案为 YES，否则为 NO。
按照编号从小到大枚举 $j$，并统计满足 $a_k \lt a_j$ 的所有 $k$ 中 $b_k$ 最大的值 $b_i$，如果 $b_i \gt b_j$ 则说明这种情况出现了
判断完 $j$ 之后，用 $b_j$ 更新位置 $a_j$，用树状数组维护前缀。
100
依次考虑 $1 \sim n$。
假设当前考虑的是 $i$，前面 $i − 1$ 个位置已经确定。
找一个等于 $B_i$ 的元素 $A_j$，并考虑把它交换到 $i$ 位置。
若 $i \lt j$，当且仅当 $A_i \sim A_{j - 1}$ 都大于 $A_j$ 的时候才可能交换。
若 $i \gt j$，当且仅当 $A_{j + 1} \sim A_i$ 都大于 $A_j$ 的时候才可能交换。
交换是不改变其他元素的相对顺序的，也就是说在将一个元素移动后，它对后面就没有任何影响了，可以直接删除。
从小到大枚举 $i$，在 $A$ 中找到 $B_i$ 下一次出现的位置 $p$，判断 $A_p$ 是不是 $A_1 \sim A_p$ 中的最小值，然后把 $A_p$ 改成无穷大，相当于删除了这个元素。
用线段树进行单点修改、区间最值的维护即可。
时间复杂度 $\mathcal O(n \log n)$。
B. 密码锁
19
$n \le 6, m \le 15$
暴力枚举每条边的定向统计强连通分量个数。
时间复杂度 $\mathcal O(2^m (n + m))$。
C. a^-1 + b problem
10
$n, m \le 1000$
暴力模拟。
时间复杂度 $\mathcal O(n m \log a)$。
20
$n \le 100000, m \le 60000, t_i = 1$
直接更新总和，整体加上 $x_i$ 相当于总和加上 $n \times x_i$。
时间复杂度 $\mathcal O(n + m)$。
30
$n, m \le 10000$
每一时刻都存在常数 $a, b, c, d$ 使得原来数列中的每一个数 $A[i]$ 都变成 $\frac{a A[i] + b}{c A[i] + d}$。
于是问题转化成每一次给出一个函数 $f(x) = \frac{ax + b}{cx + d}$，求 $\sum_{i = 1}^n f(A_i)$。
当 $c = 0$ 时可以直接求和，因此接下来假设 $c \neq 0$。
首先可以把 $f(x)$ 表示为 $f(x) = e + f \times \frac{1}{x + g}$，于是只需要考虑求原来的所有数加上某一个数 $k$ 后的倒数和就行了。
因为 $\prod_{i = 1}^n (A_i + k)$ 可以 $\mathcal O(n)$ 求出，所以可以先给答案乘上这个值，于是只需要求 $\sum_{i = 1}^n \prod_{j \neq i} (A_j + k)$，这个也是可以 $\mathcal O(n)$ 求出来的，这样就可以避免求逆元的 $\mathcal O(\log n)$。
时间复杂度 $\mathcal O(n m)$。