A. Three Castles
每一对凸包之间都存在一条直线分割它们，我们可以枚举三条直线，然后检验得到的方案。枚举直线的时候可以假设是凸包的公切线，即枚举 $(i,j)$，凸包 $A$ 是 $P_iP_j$ 左侧的点加上 $P_j$，凸包 $B$ 是 $P_iP_j$ 右侧的点加上 $P_i$。任意两条直线的限制相交就能得到想要的点集，然后检验三个点集是否都是凸包且每个点都出现一次。
检验凸包可以对于每对切线事先预处理，复杂度 $O(n^5)$。之后枚举三条切线之后就可以 $O(1)$ 判断，时间复杂度 $O(n^6)$。
由于需要枚举的量还是很多，需要进行一些剪枝，例如利用对称性，以及限制枚举的点必须在对应的凸包内以保证是切线。
B. Bitwise Beach
矩形的高和宽分别只有 $O(\sqrt n)$ 种，枚举之后求和即可。时间复杂度 $O(n)$。
C. Copy-paste
有意义的操作相当于：
- 花费 $1$ 代价将 $n$ 增加 $1$。
- 花费 $k+2$ 代价将 $n$ 变为 $kn$。
直接用二进制可以得到答案不超过 $5\log_2 n$。从 $n$ 开始倒着考虑，有用的状态也就都形如 $\left\lfloor \frac n x \right\rfloor$，每次转移是枚举除数 $k$，然后先减去 $n\bmod k$ 再除以 $k$。直接对这些状态进行 Dijkstra，因为答案很小，使用桶而不是二叉堆实现优先队列，时间复杂度 $O(\sqrt n\log n)$。
D. Deque Sort
$n$ 轮以内一定能排序：考虑形如 $x,x+1,\ldots,n$ 的后缀，这个后缀每一轮都会变长。对于剩余的前缀，我们需要将所有的前缀最大值取出来，然后将其他数翻转之后接在前面。
事实上如果我们暴力进行上述操作，需要取出的前缀最大值的总数是 $O(n)$ 的。这是因为经过若干轮操作后，数组一定形如递减段 + 中间段 + 递增段。其中中间段是从未被取出过的。每一轮过后，递增段的末尾会进入已经排序好的后缀，而取出的前缀最大值一定是递减段的开头加上中间段的一些数，然后递减段加上这些新的前缀最大值成为了新的递增段，递增段成为了新的递减段。因此我们会发现每个数进入递减或者递增段之后就会一直保持，从而取出的数总数是 $O(n)$ 的。
接下来可以用平衡树翻转直接维护，或者按照上述分析分三段维护。时间复杂度 $O((n+q)\log(n+q))$。
E. Evaluation
可以将式子的求值用矩阵乘法表示：当前的表达式形如 $A+B\cdot C$，可以用矩阵表示 $A,B\cdot C,B,1$ 之间的转移。对于所有情况求和只需将每个位置的矩阵求和之后乘起来即可。时间复杂度 $O(n)$。
F. Fix the Coloring
染色的条件相当于同色且有边相连的两个点至少有一个需要染红，但是因为可以选择一个团全部染红，这个条件并不好表示。
考虑枚举团当中的一个点 $x$，那么一个染红的点如果与 $x$ 相邻就在团中，否则就不在团中。因此限制可以写成如果 $u,v$ 不同时与 $x$ 相邻，则它们之间有边时不能同时染红；如果 $u,v$ 同时与 $x$ 相邻，则它们之间没有边时不能同时染红。这些条件都可以用 2-SAT 表示。
每次 2-SAT 需要在原图的基础上加上额外的 $O(\deg(x)^2)$ 条边，总和不会超过 $O(nm)$，因此总时间复杂度 $O(n(n+m))$。
G. Good Permutations
注意到每个递减段都是公差为 $-1$ 的等差数列，因此递减段之间是不会相交的。考虑递减段分别是 $[l_1,r_1],\ldots,[l_k,r_k]$，则 $i$ 属于 $[l_j,r_j]$ 时必定有 $a_i+i=l_j+r_j$。令 $b_i=a_i+i$，则 $b_i$ 必须递增，且每个 $b_i$ 相等的段需要选择尽可能短的区间，使得这些区间不相交。区间查询时，假设已经确定的连续两段是 $[x,y]$ 和 $[z,w]$，则有限制 $\max\{b_x+l-x,y\}<\min\{b_z+l-w,z\}$，也即限制形如 $l$ 属于某个区间，只需要用 RMQ 并且特殊处理开头和结尾的段即可。时间复杂度 $O(n+q)$。
H. House
只有最大的 $4k$ 个 $a_i$ 可能有用，因此我们假设 $n=O(k)$。检验一对 $(x,y)$ 只需要进行一轮 DP，可以做到 $O(k^2)$。至少有两种 DP 方法：$f(i,j)$ 表示选了 $i$ 个 $x$ 和 $j$ 个 $y$，至少需要用到几块木材，最后一块最少用多少；或者直接背包，但是判掉 $\sum \left\lfloor \frac{a_i}{x}\right\rfloor\ge 4k$ 的情况。问题在于如何找到可能的 $(x,y)$。
考虑确定每个木材分出几个 $x$ 和几个 $y$ 之后，有一系列形如 $ax+by\le c$ 的半平面限制。最终取到的 $(x,y)$ 要么是两个半平面的交点，要么是一个半平面和反比例函数 $xy=S$ 的切点，二者的数量分别是 $O(k^6)$ 和 $O(k^3)$。暴力枚举可以做到 $O(k^8)$ 复杂度。
想要通过需要进行剪枝，包括：
- 单调性，即如果 $x_1\le x_2,y_1\le y_2$，若 $(x_1,y_1)$ 不可行，则 $(x_2,y_2)$ 也不可行。
- 如果 $x\ge 4y$ 则不如把 $x,y$ 都变成 $\frac{x}{2}$。
加上上述剪枝后，需要检查的 $(x,y)$ 事实上并不多，但是枚举所有交点的 $O(k^6)$ 仍然难以接受。我们可以先计算单个半平面的答案，然后只保留那些可能贡献更优答案的半平面求交点。这样就可以通过了。
也可以直接二分答案，然后枚举反比例函数和半平面的交点，这样的复杂度是 $O\left(k^5\log \frac{V}{\epsilon}\right)$。其中 $O(k^3)$ 来自于每次二分需要检查的半平面个数。进一步的，如果二分的答案是 $S=x^2$，那么 $\sum \left\lfloor \frac{a_i}{x}\right\rfloor \ge 4k$ 的情况是平凡的，否则每个 $a_i$ 和反比例函数有交的半平面数量只有 $O\left(\frac{a_i}{x}\cdot k\right)$，总共 $O(k^2)$，因此可以优化到 $O\left(k^4\log\frac{V}{\epsilon}\right)$。
注：第二个做法中的分析实际上可以说明第一个做法中剪枝后半平面数量也是 $O(k^2)$，总复杂度不超过 $O(k^6)$。
I. Palindromes
把回文对应位置连边之后，我们需要计算连通块数量 $c$，则答案就是 $2^{c}$。考虑 ${a_i}$ 的最大和次大值 $x,y$，如果 $x\ge 2y$，则 $x$ 对 $y$ 没有任何限制，可以删除 $x$，将 $c$ 增加 $\left\lceil\frac{x}{2}\right\rceil-y$。如果 $x< 2y$，则可以将 $x$ 替换为 $2y-x$。不断重复上述操作直到只剩下 $0$，即可得到答案。
用堆暴力模拟上述过程，用除法优化最大值和次大值交替减小的过程，则每一轮要么删除一个数，要么使得 $x-y$ 减小一半，因此复杂度不超过 $O((n+\log N)\log n)$。
J. Jewel Guards
我们只需对每个子集计算至少有两个守卫的时间。离散化之后我们对每个时间单位分别考虑，设该时间单位中工作的守卫集合为 $T$，则我们选择的集合需要满足 $|S\cap T|\ge 2$ 才能计入该时间单位的长度。也即 $S$ 不是某个 $\overline T\cup \{x\}$ 的子集，容斥一下可以变成 $O(k)$ 个“给 $S$ 的所有子集答案加上 $v$”的操作，最后一次 FMT 即可。时间复杂度 $O((\sum c_i+2^k)\cdot k)$。
K. Multiset Variance
首先考虑最小值，由于方差就是 $\min_x \frac{1}{n}\sum_{i=1}^n (a_i-x)^2$，所以可以枚举 $x$，之后就是选若干个数，最小化平均值。所以方差最小值一定是在取单个集合的时候取到。
最大值仍然考虑枚举 $x$，这时要求平均值必须等于 $x$。设第 $i$ 个可重集为 $S_i$，$b_i=\frac{1}{|S_i|}\sum_{y\in S_i}(y-x),c_i=\frac{1}{|S_i|}\sum_{y\in S_i}(y-x)^2$，则相当于要找一组实数 $s_1,\ldots,s_n$，满足 $\sum b_is_i=0$，最大化 $\sum c_is_i$。这也就说明了方差一定能在只选两种集合的情况下取到最大值。
设选择的两个集合为 $S,T$，$s_1,t_1$ 分别为 $S,T$ 的平均值，$s_2,t_2$ 分别为 $S,T$ 的平方平均值。则需要找到 $p,q\ge 0,p+q=1$，最大化 $ps_2+qt_2-(ps_1+qt_1)^2$，这是关于 $p$ 的二次函数，一定在 $0,1$ 或对称轴处取得最值。进一步的，把 $(s_1,t_1)$ 和 $(s_2,t_2)$ 看作平面上的点，则我们需要选择线段上的一点 $(x,y)$，最大化 $y-x^2$。容易发现一定是在上凸包取到最大值。这也可以代替上面的分析说明一定取不超过两种集合。
时间复杂度 $O(n\log n)$。