将 1 放在 n x n 个零板中，使所有行和所有列都具有相同的奇偶校验-解网

问：

我正在执行以下任务：

给定一个 n x n 板，上面有 m 个按钮，按下至少一个按钮，使每行和每列中按下的按钮计数相同。

输入

n， m
x 1， y₁
x 2， y₂
...
x m， y_m

其中 n 是方板边的长度，m 是板上的按钮数，x i、y i 是^第 _i 个按钮的坐标。

输出

如果没有解决方案，则输出“NO”。

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

约束

n ≤ 10⁵

m ≤ n 2，m ≤²⋅10⁵

我的解决方案尝试：

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

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

例：

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

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

我们如何有效地解决这个问题？

算法数学组合学

创建一个大小为 2n 的数组。索引 0 到 n-1 将对应于行，而索引 n 到 2n-1 将对应于列。R
遍历转换为索引元组的按钮，其中：(x,y)(i,j)Ri < j(x,y) => (y, x+n)
每个元组都是其最小索引的候选代表。如果为空，则设置，然后继续执行下一个元组。R[i]R[i] = (i,j)
否则，让我们先创建一个包含和最小索引的新元组。如果，则这是新的最小索引的新候选代表。否则，返回 YES，因为您已经找到了该问题的偶校验解决方案。(i, j2) = R[i]jj2j!=j2

请注意，每个候选代表元组都表示切换某些按钮集的效果，当我们组合两个元组时，我们将这些集合组合在一起。

如果已处理所有按钮但未返回 YES，则没有偶校验解决方案，并且所有按钮都是线性独立的。

要查看是否存在奇偶校验解决方案，请循环访问，为具有错误奇偶校验的行或列选择每个代表，然后翻转与其两个索引对应的行和/或列。如果发现奇偶校验的行/列没有代表，则返回 NO，因为没有解决方案。如果你坚持到最后，那么你已经将所有行/列设置为奇数奇偶校验，答案是肯定的。R[0]R[2n-1]

实现比解释更简单：

def sameParity(n, buttons):

    reps=[0]*(2*n)
    for (x,y) in buttons:
        i = y
        j = x+n
        while reps[i] > 0:
            j2 = reps[i]
            if j2 == j:
                # Even parity solution
                return True
            i = min(j,j2)
            j = j + j2 - i # the other one
        reps[i] = j

    # no even parity solution. try odd
    parities = [False]*(2*n)
    for i in range(2*n):
        if not parities[i]:
            if reps[i] < 1:
                return False
            parities[i] = True
            parities[reps[i]] = not parities[reps[i]]
    return True 

N = 3
buttons = [(2,1),(1,2),(0,1),(1,1),(1,0)]
print(sameParity(N, buttons))

将 1 放在 n x n 个零板中，使所有行和所有列都具有相同的奇偶校验

Placing 1 in n x n board of zeroes, such that all rows and all columns have same parity

输入

输出

约束

我的解决方案尝试：

例：

评论

评论