CFER 136 小记

我来诈个尸。

C Card Game

考虑 \(n=60\) 时，59 和 60 这两张 cards 的三种情况。

• 若 Alex 拿到了 60 她就赢了。
• 若 Boris 拿到了 59,60 他就赢了。
• 若 Alex 拿到 59，Boris 拿到 60，那么相当我们需要求解 \(n=58\) 的情况。

于是就是 \(n\) 从小到大推。假设 \(f_n\) 是共 \(n\) 张 cards 时先手必胜的情况。

则有 \(f_i= C(i-1,\frac{i}{2}) + [C(i-2,\frac{i}{2}-1) - f_{i-2} - 1]\)。

D Reset K Edges

二分答案。然后贪心地从深度最大的节点的 \(mid-1\) 代父亲开始剪。

用了树状数组+dfs序维护子树覆盖单点查值，不过后来发现暴力弄也没啥问题，毕竟每个点最多被删掉一次。

E Cleaning Robot

显然是 dp。问题是怎么 dp 呢？

假设机器人现在在 \((r,c)\)。那么我们关注 \((r',c)\) 是否 dirty。（\(r'+r=3\)，它们不在同一行)

• 如果 \((r',c)\) 不是 dirty 的，可以证明直接让机器人往右边走一格是最优的，无论后面是什么情况。

• 如果 \((r',c)\) 是 dirty 的

  • 第一种方法：弃之不顾。不管 \((r',c)\)，直接跑到右边一个，cost 加一。
  • 第二种方法：打扫该点。如果 \((r,c+1)\) 非 dirty，那还好说。但是如果 \((r,c+1)\) 是 dirty 的，我们就要把 \((r,c+1)\) 打扫掉（cost 加一），然后才能去打扫 \((r',c)\)。注意，第二种方法，我们直接转移到 \((r',c+2)\)（Think why?)

然后就可以 dp 了。btw 我们采用的是递推式的 dp。