hdu7419 2022杭电杯 Alice and Bob(博弈)(思维)

给出$n$个非负整数，Alice的目标是出现为0的数，否则Bob获胜。
可以对数进行如下的操作：首先Alice将现有的数分成两个集合，Bob会将其中一个集合的数全部删掉，并且将另一个集合的数全部减掉$1$；如此循环。

仔细思考会发现，Alice获胜需要值为$i$的数$2^i$个。

我的一种贪心想法，从大到小的枚举数，对于一个值为$i$的数而言，它可以生成$\lfloor \frac{a_i}{2}\rfloor$个$i-1$。于是就这样去考虑这些数能不能生成$0$。好像并不是很好做。

正解给了另一种神奇的解释。这个解释很好地表述了博弈问题中，恢复“必胜态”的思想。就是说如果对手无论怎么操作，你都能将状态转回到你想要的状态，那么这局比赛必拿下。

在这题中，正解的作者对题意进行了惊天大改动。说把一个数$i$看成$2^{n-i}$，获胜目标改成能否有数变成$2^n$(对应的$i=0$)，每次的Bob的删除操作对应的将一部分数删掉；另一部分在原题中是减1的操作，在他这就变成了乘$2$。

所以，对于Bob每次将数删去一半，如果Alice能够将数再乘回来，保证数的和仍然是大于等于$2^n$，那么就能获胜。所以Alice的操作是尽量让数平均分配。这个想想就是很容易做到的，也是可行的。(就是说如果数的和是大于等于$2^n$，很容易找到一种方案，能够让Alice分成的两个集合都大于等于$2^{n-1})$。

从正解的角度来看，现在要判断的就是所有数的$2^i$之和，是否大于等于$2^n$。

后记：答案的想法还是可以推出来的。在分析状态的时候，可能是在写$122$是必胜态，那么$13333$也是必胜态。其实$13333$写着就有点违反自己的感受，命名是加了一倍，但是数字只是加了$1$。然后大胆地用$4$表示$3$，就成了$14444$是必胜态。这样容易发现，会不会把1看作4,4看作$1$,一个$1$就是$4$,四个$4$和也是$4$，更容易悟到什么。