不同组合算法（Candy Splitting）

Question

昨天我参加了谷歌代码塞班竞赛。有那个糖果分裂问题。 http://code.google.com/codejam/contest/dashboard?c=975485#s=p2

我设计的，基本上为尝试帕特里克的桩与肖恩的桩，检查所有不同的组合，如果他们有相同的帕特里克值的算法，最后选择，将最大限度地发挥肖恩的份额组合。该算法适用于小型输入文件。对于大型问题，我遇到了内存问题，输出从未出现。我相信这是另一种解决这个问题的方法，它不需要考虑所有组合。谁能帮忙？

Answer 1

对于小的输入，糖果的数量很少（高达15）。搜索所有可能的案例将包括2^15 = 32768的可能性，可以在毫秒左右检查。但高达1000个糖果（大量输入），可能的组合数量达到2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376。现在这个数字有点太大了，即使你运行了几年的程序，你也不会得到结果。

有一些意见这使得高效的程序进行这个帮助：

• 像@Protostome指出，帕特里克的总和实际上是XOR运算的总和。
• 再次像@Protostome指出的那样，如果它是可解的，则所有糖果的异或将为0.原因是这样的：如果在两个分区中可能具有相同的异或值，则将两者的异或分区将是a xor a = 0。
• 如果可以分割，那么所有糖果的xor总和为0.但是，如果我们从整组糖果中移除一个糖果，它将变成非零。特别是，

。

也就是说，我们可以通过从整个集合中取出一个糖果来将它们分成两部分。为了最大化左半部分的算术总和，我们必须取最低值的糖果。所以，高堆糖果的算术总和是所有糖果的总和 - 最低的价值！

因此，我们有：

1. 如果所有糖果的XOR是零，它是可解
2. 如果它是可解的，总和为整个列表的总和 - 最低值。