将 1 放入 n x n 块零中，使得所有行和所有列具有相同的奇偶校验

Question

我正在执行以下任务：

给定一块 𝑛 x 𝑛 板，以及上面的 𝑚 按钮，按下至少一个按钮，使得每行和列中按下的按钮的数量具有相同的奇偶性。

输入

𝑛，𝑚
𝑥₁，𝑦₁
𝑥₂，𝑦₂
...
𝑥_𝑚，𝑦_𝑚

其中𝑛是方板边长，𝑚是方板上按钮的数量，𝑥_𝑖、𝑦_𝑖是第𝑖^第按钮的坐标。

输出

如果无解，输出“NO”。

否则，输出“YES”，后跟按下按钮的索引。

限制

• 𝑛≤10⁵
• 𝑚 ≤ 𝑛²，且 𝑚 ≤ 2⋅10⁵

我的解决方案尝试：

我们可以将输入想象为全零的 𝑛x𝑛 矩阵。某些矩阵单元格可以设置为 1（这些是“按钮”）。我们必须将至少一个单元格设置为 1。我们可以将多个单元格设置为 1，但仅限具有此功能的单元格（“按钮”）。如果我们能找到一种方法给每列和每行一个全偶数或全奇数的总和，我们就有了一个解决方案。

我发现，在每行每列的按钮之和为偶数且存在这样的答案的情况下，顶点（按钮）通过与同一行或列中的另一个顶点合并而形成一种循环。但这些信息并没有真正给我任何东西；计算复杂度仍然会很高。

示例：

这里，“B”是一个按钮，“-”是没有按钮的单元格。此示例的唯一解决方案是按下所有按钮，使所有行和列的奇偶校验均为 1。

BBB-
---B
---B
---B

如何有效解决这个问题？

Answer 1

这个问题很烦人，因为我认为检测偶校验 YES 和奇校验 YES 的最佳算法是完全不同的。

偶数奇偶校验

偶校验问题可以在O(m)时间内解决。

制作一个二分图，其中一侧的每行有一个顶点，另一侧的每列有一个顶点，以及连接行和列的每个按钮的边。

如果该图中存在任何循环，则答案是“是”。

有很多方法可以检测无向图中的循环。考虑到您输入的具体形式，我将使用不相交的集合数据结构，如Kruskal算法中那样，这样我就不必实际构建图表。

奇校验

为了检测所有行和列都具有奇校验的解决方案，我建议采用类似于“高斯消除”的过程。这可能需要长达 O(nm) 的时间：

创建一个大小为 2n 的数组

R
• 。索引 0 到 n-1 将对应于行，而索引 n 到 2n-1 将对应于列。迭代按钮，将
(x,y)
• 转换为

  (i,j)

  中的索引

  R

  元组，其中

  i < j

  ：

  (x,y) => (y, x+n)

  每个元组都是其最小索引的候选者
代表。如果
• R[i] 为空，则设置 R[i] = (i,j)

  ，然后继续下一个元组。

  否则，让 

  (i, j2) = R[i]
首先创建一个包含
• j

   和 

  j2

   且索引最小的新元组。如果 

  j!=j2

  ，那么这是新的最小索引的新候选代表。否则，它是没有用的，你可以丢弃它并移动到下一个按钮。

  请注意，每个候选代表元组代表切换某些按钮
set

的效果，当我们组合两个元组时，我们会组合这些集合。

处理完所有按钮后，如果您为每一行和每一列找到了一个有代表性的元组，那么答案就是“是”。