Codeforces-190

没坑才敢发上来的。

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)\) 。