0%

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