algorithm - 用相等的 XOR 划分数组

Question

我不知道怎么解决这个问题>>

给定一个整数数组，我们需要将该数组分成两部分，使得

1) 第一组的异或等于第二组的异或

2) 两部分元素之和之差最大。

例如:

如果给定的数组是[4,2,6]

那么可以分为[2],[4,6],

          where xor(2) = 010
                xor(4,6) = 100^110 = 010 = xor(2)

两部分之和的差值 = (4+6)-2 = 8(满足上述约束的最大可能差值)。

(如果不是第二个约束，将数组分成和相等的部分就足够了)。

Answer 1

这是一个技巧问题。

如果您有整数 a1...an 并且您可以将它们分成两部分以使它们的 XOR 相等，这就意味着 a1 xor a2 xor ... xor an 等于零。当它成立时，任何分区都有效，例如(a1) xor (a2 xor a3 xor ... xor an) == 0 由上式可知 a1 == a2 xor ... xor an。因此任何分区都有效。鉴于此，您只需选择一个空分区和完整分区(如果允许)，或者将最小整数放入单例分区并将其他所有内容放入第二个分区。