Contest Info

practice link

Solutions

A. Hide and Seek

签到题。

B. Chladni Figure

签到题。

C. Thanos Nim

题目大意：有 \(n\) 堆石子，\(n\) 为偶数，两个人轮流行动，每次选择 \(\frac{n}{2}\) 堆石子，每堆石子取走正整数个，不能取者输。问先手胜还是后手胜。

题解：假设当前状态下 \(n\) 堆石子均非空，那么当前玩家不能拿空任意一堆石子，否则就输了。所以当前的状态等价于每一堆石子数量都减少 \(1\)。这样递归下去，非空石子堆一定 \(<n\)，这样就简单了，如果非空石子堆数 \(\ge\frac{n}{2}\)，那么先手胜，否则后手胜。

D. Palindrome XOR

裸的无向图 2-SAT

E. Rainbow Coins

题目大意：交互题。有 \(n\) 个物品，分别是 RGB 三种颜色。你最多可以询问 \(7\) 次，每次给出 \(k\) 个 pair，每个物品只能出现最多 \(1\) 次，交互器会告诉你每一对物品颜色是否相同。最后要求你将物品分成 \(3\) 堆，使得每堆物品的颜色相同，但是不要求你知道每堆具体的颜色。

题解：先说明分类的策略。首先问出每一对相邻的物品的颜色是否相同，这样我们就可以合并所有相邻且颜色相同的物品，得到的序列所有相邻的物品颜色都不同，这样之后再询问每隔一个物品的物品对颜色是否相同就能得到答案了。询问的方式是：第一次 \((1,2),(3,4),(5,6),\cdots\)，第二次 \((2,3),(4,5),(6,7),\cdots\)，第三次 \((3,1),(4,2),(7,5),(8,6),\cdots\)，第四次 \((5,3),(6,4),(9,7),(10,8),\cdots\)，这样用 \(4\) 次询问就得到了答案。

F. Zigzag Game

二分图，pass。