用相等的XOR分割数组

Question

我不知道怎么回事这个问题>>

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

1)第1组的xor等于第2组的xor

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等于零.当它成立时,任何分区都可以工作,例如(a1)xor(a2 xor a3 xor ... xor an)== 0,所以它必须是a1 == a2 xor ... xor an.因此任何分区都有效.鉴于此,您只需选择一个空分区和完整分区(如果允许),或将最小整数分配到单个分区中,并将其他所有内容放入第二个分区.