UOJ Round #16
A. 破坏发射台
8
$n \bmod = 1$ 且 $n \le 11$
$m \le 11$
暴力枚举所有染色方案判断是否合法。
时间复杂度 $\mathcal O(n^m)$。
40
$n \le 11$
利用最小表示法将状态去重。
时间复杂度 $\mathcal O(n!)$。
56
$n \bmod 2 = 1$ 且 $n \le 10^7$
设第一格的颜色为 $A$，然后设个一元二进制状态表示当前格的颜色是否为颜色 $A$。
设 $f[i][0 / 1]$ 表示第 $i$ 格的颜色是否为颜色 $A$ 的合法方案数，递推即可。
时间复杂度 $\mathcal O(n)$。
64
$n \bmod 2 = 1$ 且 $n \le 10^9$
使用矩阵快速幂优化。
时间复杂度 $\mathcal O(\log n)$。
88
$n \bmod 2 = 0$ 且 $n \le 10^7$
设第一格的颜色为 $A$，设第 $\frac{n}{2} + 1$ 格的颜色为 $B$，然后设个二元三进制状态表示第 $i$ 格和第 $\frac{n}{2} + i$ 格的颜色是否为颜色 $A$ 或颜色 $B$（$1 \le i \le \frac{n}{2}$）。
设 $f[i][0 \sim 8]$ 表示第 $i$ 格的合法方案数，递推即可。
时间复杂度 $\mathcal O(n)$。
100
$n \bmod 2 = 0$ 且 $n \le 10^9$
使用矩阵快速幂优化。
时间复杂度 $\mathcal O(\log n)$。
B. 破坏蛋糕
25
$n = 3$
保证前 $n$ 条中存在两条直线 $L1$ 与 $L2$，使得其他直线要么与 $L1$ 平行，要么与 $L2$ 平行
有限的区域分别是三角形和平行四边形，求出这个三角形和平行四边形，在每一段上选关键点判定即可。
时间复杂度 $\mathcal O(n)$。
50
$n \le 1000$
在每一段上选关键点判定，使用半平面交。
时间复杂度 $\mathcal O(n^2 \log n)$。
65
$n \le 5000$
把所有直线按照斜率排好序，单次半平面交 $\mathcal O(n)$。
每条直线方向只会改变一次，而且还是改变了 $\pi$，把这条直线拿出来再插回去，单次排序 $\mathcal O(n)$。
时间复杂度 $\mathcal O(n^2)$。
考虑另一种常数更小的判定方法，把所有直线面向判定点一侧法向量的斜率拿出来极角排序，如果有两个相邻的法向量的极角查 $\ge \pi$ 就说明出现了一个开口，这个区域是无限的。
100
$n \le 10^5$
每次只修改了一个法向量，而且只需检测相邻的法向量，可以用平衡树来做，事实上一个 std::set 足矣。
注意转过一圈时的边界情况。
时间复杂度 $\mathcal O(n \log n)$。
C. 破坏导蛋
20
$n \le 10^3$
$m \le 10^3$
暴力枚举。
时间复杂度 $\mathcal O(10^6)$。
40
$\lvert x_i \rvert, \lvert y_i \rvert \le 100$
枚举点的横坐标把二维的限制降至一维，这样询问就变成了询问横坐标等于 $x$ 的点中纵坐标在某一个区间内的点数，对每一个横坐标预处理一下前缀和即可。
时间复杂度 $\mathcal O(\lvert x \rvert \lvert y \rvert + n + m)$。