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。因此任何分区都有效。鉴于此，您只需选择一个空分区和完整分区（如果允许），或者将最小整数放入单例分区并将其他所有内容放入第二个分区。