题解：P10609 排除干扰

· · 题解

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

首先考虑特殊性质 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