2

我们有一个二维数组，左上角的数字为 0。然后用数字填充数组的其余部分，以便每个索引包含可能既不存在于同一行也不存在于同一列的最小正整数。

例子：

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
  1  0  3  2  5  4  7  6  9  8 11 10 13 12 15 14 17 16
  2  3  0  1  6  7  4  5 10 11  8  9 14 15 12 13 18 19
  3  2  1  0  7  6  5  4 11 10  9  8 15 14 13 12 19 18
  4  5  6  7  0  1  2  3 12 13 14 15  8  9 10 11 20 21
  5  4  7  6  1  0  3  2 13 12 15 14  9  8 11 10 21 20
  6  7  4  5  2  3  0  1 14 15 12 13 10 11  8  9 22 23
  7  6  5  4  3  2  1  0 15 14 13 12 11 10  9  8 23 22
  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7 24 25
  9  8 11 10 13 12 15 14  1  0  3  2  5  4  7  6 25 24
 10 11  8  9 14 15 12 13  2  3  0  1  6  7  4  5 26 27
 11 10  9  8 15 14 13 12  3  2  1  0  7  6  5  4 27 26
 12 13 14 15  8  9 10 11  4  5  6  7  0  1  2  3 28 29
 13 12 15 14  9  8 11 10  5  4  7  6  1  0  3  2 29 28
 14 15 12 13 10 11  8  9  6  7  4  5  2  3  0  1 30 31
 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0 31 30
 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  0  1
 17 16 19 18 21 20 23 22 25 24 27 26 29 28 31 30  1  0

给定这样的数组中的行和列，我需要能够在相对较新的台式 PC 上在一秒钟内找到指定索引中的数字（对于小于一百万的行和列）。到目前为止，我的蛮力尝试都是徒劳的，这显然不是我想要的方式。大概必须有一种方法可以在线性时间（？）内找出有问题的数字，这不需要计算数组中所有前面的数字。

4

1 回答 1

2

观察表明，运算符是按位的XOR（将每个操作数表示为二进制数，将相应的位异或，读取为二进制）。

现在证明它是异或：

由于固定一个参数的 XOR 是另一个参数的双射，因此满足“既不存在于同一行也不存在于同一列”。

现在只需证明“最小”部分就足够了，即如果我们减少任一操作数，任何较低的值都已经出现：

foreach A >= 0, B >= 0, F >= 0:
  (A xor B > F) => (exists D: D xor B = F) or (exists E: A xor E = F)

或等效地

foreach 0 <= A, 0 <= B, 0 <= F < (A XOR B)
  (exists D: D xor B = F) or (exists E: A xor E = F)

请注意，我们不再关心我们的运算符，我们正在证明 XOR 的最小性。

定义C = A xor B

如果A = 0, B = 0, 则满足极小性。

现在，如果A和B具有相同的幅度（相同的位长），那么清除两者的最高位不会改变C。清除最高位是向矩阵中原点的平移，因此如果平移后上方或左侧存在较小的值，则它在平移前处于相同的相对位置。

A并且B必须具有不同的量级才能成为反例。XOR（以及正在考虑的运算符）是对称的，所以假设A > B.

如果F大于A，则不小于 ，因此不是反例。

如果F与 具有相同的幅度，则清除和 中A的最高位。这是表中的翻译。它会更改值，但不会更改它们的顺序，因此如果在平移后上方或左侧存在较小的值，则它在平移前处于相同的相对位置。AF

如果F具有比 更小的量级A，则根据鸽笼原理和 XOR 的性质，存在一个D量级小于A的D xor B = F。

摘要： XOR 满足强加于解的条件的证明来自 XOR 的对称性、其保幅特性和双射特性。我们可以A xor B通过减少和挑战找到每个更小的元素A，B直到它们都为零或不同大小（此时我们应用鸽巢原理来证明可以在不实际对抗的情况下对抗挑战）。

于 2012-12-19T00:17:18.930 回答