没坑才敢发上来的。

cgy4ever 是我最喜欢的出题者之一。他出的题代码短，思考难度高，而且非常好玩。

Solution

A

首先模拟一次，求出最后的 $\Delta x, \Delta y$ ，然后依次枚举路径上经过的每个点，判断是否经过一定的平移后和终点重合。判断是否能重合要特别小心，不能直接算除法：如果 $\Delta x = 0$ ，那么这个点必须和终点的 $x$ 坐标一定相同，否则应该通过模来判。

变量忘记初始化导致连续两次 WA pretest2 好囧。不过最囧的是 FST 了……

B

分两种情况讨论。

1. 最后 $n$ 张卡都被打完了。这种情况下肯定是先用恰好比他属性点高的最小的卡去打，然后剩下的卡一张一张打过去。
2. 最后 $n$ 张卡没有被打完。很明显，打 DEF 的怪是不科学的，于是用我方从高到低的卡依次打对方从低到高的 ATK 卡，直到打不动为止。

C

考虑字母 A 的放置。显然 A 应该出现，而且出现最多一次。如果出现两次的话，这两个点之间的路径中就没有比 A 更高的了。不妨设标号为 A 的节点为点 $x$ 。

考虑把 $x$ 删掉，原树会分裂成若干棵树，任意跨过点 $x$ 的路径都是合法的，因为不会再出现 A 了，且 A 是最高的，所以只需要依次递归处理就好了。

于是 $x$ 该怎么选择呢？一种较优的方法是点分治，每次选择树的质心，递归层数不会超过 $\lceil \log_2 n \rceil < 26$ 。

D

令 $f_{i, j}$ 表示 $(i, j)$ 最后有没有被翻过来，可以证明，只要满足以下两个条件，那么 $f$ 就是可能的：

1. $\forall 1 \leq i \leq x, f_{i, j} + f_{i, x} + f_{i, j+x} = 0$
2. $\forall 1 \leq j \leq x, f_{i, j} + f_{x, j} + f_{i+x, j} = 0$

于是我们枚举 $f_{1, x}, f_{2, x}, \dots, f_{x, x}$ ，接下来每个 $f_{x, i}$ 的最优解是无关的，求出每个 $f_{x, i}$ 的最优解就好了。

E

令 $f_{i, j}$ 表示把 $[1, j]$ 这一段分成 $i$ 份的最小总代价。

于是我们要优化这么一种 dp ：

$$f_i = \min(g_j + w_{i + 1, j})$$

容易知道， $i$ 的决策是递增的，于是我们有一种很牛逼的方法来利用决策单调性，伪代码如下：

def work(L, R, dl, dr) :
	m = (L + R) / 2
	for i = dl to dr :
		update g[m] using i
	if L == R : return
	let dm be the optimal decision of m
	work(L, m - 1, dl, dm)
	work(m + 1, R, dm, dr)

递归层数是 $O(\log n)$ 的，每层的总运算量是 $O(n)$ ，总复杂度为 $O(nk \log n)$ 。