n×n棋盘按钮奇偶性一致按压方案高效求解

问题描述 #

给定一个n×n的棋盘，上面分布着m个可按压按钮（坐标为(xᵢ, yᵢ)，索引从1开始）。要求按压至少一个按钮，使得最终每行、每列中被按压按钮的数量的奇偶性完全一致（即所有行和列的奇偶性全为偶数，或全为奇数）。若无解则输出NO，否则输出YES及被按压按钮的索引。

约束条件：

• n ≤ 10⁵
• m ≤ min(n², 2×10⁵)

初步思路 #

我最初将问题转化为0-1矩阵模型：棋盘初始全为0，按钮位置可设为1（代表按压）。目标是选择至少一个按钮位置设为1，使得所有行和列的和的奇偶性统一（全偶或全奇）。

我观察到如果目标是全偶的情况，可行解对应的按钮位置可能形成同行同列合并的环，但这个结论对降低时间复杂度帮助不大，无法直接应用到大规模数据场景。

高效解法 #

我们分两种目标情况分别处理，只要其中一种情况存在解，即可输出结果：

1. 目标：所有行和列的奇偶性为奇数（全奇） #

核心逻辑

选择所有按钮后，统计每行/列按压数的奇偶性：

• 设row_parity[x]为行x按压数的奇偶性（1=奇，0=偶）
• 设col_parity[y]为列y按压数的奇偶性（1=奇，0=偶）
• 计算a：row_parity中0的数量；b：col_parity中0的数量

全奇目标可行的必要条件是a == b（否则行/列奇偶性总和的模2矛盾），在此基础上：

• 若a == 0：直接输出所有按钮的索引，此时所有行/列的奇偶性已为奇数。
• 若a > 0：需要找到a个按钮，每个按钮位于row_parity[x]=0的行和col_parity[y]=0的列。选择所有按钮后，取消按压这a个按钮，即可让所有行/列的奇偶性翻转成奇数。

2. 目标：所有行和列的奇偶性为偶数（全偶） #

核心逻辑

全偶目标等价于在二分图中找一个非空欧拉子图（所有节点度数为偶）。我们用并查集实现：

• 将行视为1_{n的节点，列视为n+1}2n的节点。
• 每个按钮(x,y)对应二分图中的一条边，将节点x和n+y合并。
• 遍历所有按钮，若存在某个按钮(x,y)使得x和n+y在同一个连通分量中（即存在环），则该环上的按钮子集即为解（环中每个行/列的按钮数为偶数）。

3. 结果判断 #

• 若上述两种目标中任意一种存在解，输出YES及对应的按钮索引。
• 若两种目标均无解，输出NO。

示例验证 #

题目给出的示例棋盘：

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

n=4，m=6。统计后row_parity全为1，col_parity全为1，即a=0、b=0，直接输出所有6个按钮的索引，符合要求。

复杂度分析 #

• 预处理统计：O(m)时间，遍历所有按钮一次。
• 全奇目标处理：O(m)时间，遍历按钮筛选符合条件的项。
• 全偶目标处理：O(m α(n))时间，α为阿克曼函数的反函数，可视为常数。
• 整体复杂度为O(m)，完全适配题目约束。

内容的提问来源于stack exchange，提问作者user8593752