题解：CF1839E Decreasing Game

· · 题解

我们声称后手必胜当且仅当原序列存在一个子序列满足子序列内的和等于整个序列总和的一半。

显然这是充分的，因为任意时刻无论先手如何操作，后手操作另一个子序列的任意一个数。两个子序列减小量总相同，所以最后先手必败。

反之，先手每次任意操作一个数，后手操作后必定仍然不存在一个子序列和为整体的一半。这是因为你考虑若存在，容易反证本来也存在。

背包即可。