自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:43:06，当前版本为作者最后更新于2022-11-12 21:12:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非常棒的题，听 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$ 行互不相同。