P8851 题解 『JROI-7』T2nz.

· · 题解

非常棒的题，听 rsy 讲的解法。

当双方都采取最优策略时，答案为 2^n。

为了证明这点，我们可以证明，先手可以让答案 \ge2^n，后手可以让答案 \le 2^n。实际上，证明了这点就解决了题目。

后手策略：

将每行 \{1,2\},\{3,4\}\dots \{2n-1,2n\} 进行分组。每次先手下一个位置，后手下该组的另一个位置。

显然每行有 n 组，共有 2^n 个状态，答案 \le 2^n。

先手策略：

可以保证前 2^n 行互不相同，这个策略也是满足题目要求的。

考虑目前在下某一行。找到之前的行中有可能成为该行的所有行，即将每行抽象为棋子颜色和棋子位置的二元组集合，之前的行的集合包含当前该行的集合。对于这些行，计算出每一列存在的 0 的个数，选择 0 最多的一列下。

设这里有 x 行，0 的总数为 nx，那么根据抽屉原理，0 最多的一列包含 \ge \dfrac x 2 个 0。

所以，选择 0 最多的一列下可以至少排除 \dfrac x 2 行，下 n 次可以排除 \dfrac x {2^n} 行，所以前 2^n 行互不相同。