-2

A[]给定一个大小为n<=100000和的数组0<=A[i]<=2^64，并且 的每两个相邻元素A[]在其二进制表示中恰好有一个不同的数字。现在我们必须检查数组中是否存在任何4元素，例如和。A[i1],A[i2],A[i3] and A[i4]1<=i1<i2<i3<i4<=nA[i1] xor A[i2] xor A[i3] xor A[i4] = 0

4

6 回答 6

4

提示： 在这些规则下，两个数字异或可以为零吗？为什么或者为什么不？这两个数字相互之间会是什么样子？

于 2012-07-02T22:27:56.193 回答
4

由于两个相邻的数字相差一个二进制位，因此将两个相邻的数字异或的结果非常可预测：

x表示其值无关紧要的位，但与对应的x下方/上方相同。

        xxxxxxxxxxxxx1xxxxxxxxxxxx
xor:    xxxxxxxxxxxxx0xxxxxxxxxxxx
__________________________________
        00000000000001000000000000

对于您描述的集合中的任何两个相邻数字都是如此。

如果你能找到另一对相邻的数字，它们相差相同的位，它们也会异或到相同的值：00000000000001000000000000

最后，对这两个值进行异或运算肯定会给你一个零的最终答案。

所以你想要的算法看起来像：

  • 识别数字与其后继位之间的不同位（位 0-63）
  • 找到另一对也与步骤 1 中标识的相同位不同的数字。

这些是你的 4 个价值观。

请注意，如果 N > 64，那么根据鸽巢原理，必须有这样的解决方案。
如果N <= 64，可能有这种形式的解，也可能有另一种形式的解，我这里就不描述了。

还有其他约束也可以找到 4 个异或 0 的数字。
但这可能是搜索解决方案的最简单方法。
但是，无法以这种方式找到解决方案并不能保证没有解决方案。

于 2012-07-03T20:26:39.943 回答
2

提示：查看异或的真值表：

A | B | Output
- + - + - - - 
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

现在，什么二进制数与 10101 异或为 0？

这些是要查找的数字类型。

编辑：一旦你发现这些数字之间的关系是什么，你似乎从你对@abelenky 的回答的评论中得到了，你必须看看问题的其他部分。由于每个相邻元素在其二进制表示中都有一个不同的数字，这对于我们正在寻找的两个相邻元素的可能性意味着什么？

于 2012-07-02T22:30:29.073 回答
1

这是来自 CodeChef 目前正在进行的算法竞赛的一个问题。问题的链接是http://www.codechef.com/JULY12/problems/GRAYSC。所以这是不公平手段的使用，应该删除问题。

于 2012-07-05T21:12:05.860 回答
0

提示：如果您完全卡住，请尝试 O(n^4) 解决方案：

for i = 0 to N-3
  for j = i+1 to N-2
    for k = j+1 to N-1
      for l = k+1 to N
         if a[i] XOR a[j] XOR a[k] XOR a[l] is equal to 0 then
           print a[i], a[j], a[k], a[l]
于 2012-07-03T10:49:36.610 回答
0

仔细观察两个相邻数字的异或的所有可能值，总共有多少不同的值是可能的？一旦你弄清楚了这一点，你就会得到答案。

于 2012-07-03T02:03:43.713 回答