自动搬运

查看原文

来自洛谷，原作者为

	Graphcity 循此苦旅，终抵繁星。

搬运于2025-08-24 22:59:37，当前版本为作者最后更新于2024-06-17 08:34:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

游戏是这样的，先手只需要留住一张牌，而后手需要考虑的事情就多了。

首先考虑特殊性质 B。有结论：如果存在全为 1 的行，那么先手必胜，否则后手必胜。

我们在 $a$ 这个矩阵上考虑问题。一个 $r_i$ 对应一行，如果 $r_i=0$ 代表删去这一行；一个 $m_i$ 对应一列，如果 $m_i=0$ 代表删去这一列。所以如果有一行全为 1，那么先手只需要保证最后留下来的是这一行即可，其它随便操作。

接下来我们证明不存在全为 1 的行时，后手必胜。考虑如下策略：当后手操作时，如果存在一个 $m_i>1$，那么就抽掉这一张卡牌，直到所有 $m_i$ 均等于一为止。那么在接下来的每一轮，当后手进行操作时，总有剩下的行数小于列数。

根据抽屉原理，我们在每一行里面任意标记一个 0 的位置，那么至少存在一列没有被标记。我们把没有被标记的列删去即可，仍然可以变成不存在全 1 行的情况。如此操作下去，最后剩下的一个位置一定是 0。

考虑一般情况，我们可以二分 $mid$，将 $\ge mid$ 的赋值为 1，$<mid$ 的赋值为 0，那么如果存在全 1 行则代表答案 $\ge mid$。实际操作中，所有行的最小值里面，最大的那一个就是答案。

直接按上述方法模拟即可做到 $O(nm)$。

Code