CF 1516C

我们最多需要移除几个元素就能达成题目的要求？

提示一的答案：一个，证明见解答。

如何验证初始给定的序列是否已经满足要求？看看这么小的数据范围（$100\times 2000=2\times {10}^5$），能否联想到一类同样具有这么小的数据范围的题目？

提示三的答案：背包dp。

先证明提示一、二的结论：最多只需要移除一个元素就能满足要求。

考虑一个初始能够划分成两个元素和相同部分的序列。如果序列中含有一个奇数，则删去该奇数一定能够满足条件（因为此时整个序列的元素和为奇数）；若没有奇数，考虑移去一个 $2$ 就能满足条件，因为此时序列中不可能存在两个 $1$ 分配到两个序列中来配平；若不存在 $2$ 则考虑移去 $4$，以此类推就能证明该结论。该证明过程也给出了当我们需要删去一个元素时删掉什么样的元素：对整个序列所有数的二进制表示中 $1$ 所出现的最低位数，在这一位的值恰为 $1$ 的任意元素。白话说就是令整个序列的所有数不停整除 $2$，任意一个最先变为奇数的数。

那么如何检查序列是否已经满足题目要求的条件，也即是否存在一个子序列的元素和恰好为整个序列和的一半？考虑到这么小的数据范围，我们能轻易联想到背包 dp。与普通的背包 dp 不同，我们需要的是 恰好 装满背包的情况，不过转移状态时只需要转移可行性即可。