CF1839E

发布时间 2023-08-23 21:37:52作者: FOX_konata

原题

翻译

直接说结论:如果存在一种方案使得序列中最后得到的数为0,则后手必胜,否则一定先手必胜

证明:如果存在一种方案满足条件,则无论对面选什么数,我们都可以选一个数,来引导对方向我们的决策走;相反的,如果不存在这样一种方案,我们无论如何操作都无法走向决策

这时直接暴力处理,复杂度为\(O(n^n)\),无法接受

但我们发现我们这些操作相当于为每一个数加上正负号,并且保证必须至少有一个负号

于是我们可以优化一下暴力,暴力枚举正负号,复杂度\(O(2^n)\)

我们再考虑优化,我们可以把数分成两类,使得两类内所有数的和相等,如果存在这样一种方案,则后手必胜,否则一定先手必胜

证明:如果对方每次从某一类中取出一个数,我们可以在另一类中取出另一个数,把他们差的绝对值塞回去

这就变成了能否凑出两组数的和相等,这变成了一个背包问题,我们可以\(O(n^3)\)解决这个问题