题目大意：
给出n+1堆石子，前n堆石子的数量是a[i],最后一堆只有1个石子，但是具有魔力
拿走该石子的一方可以选择接下来是进行普通的Nim游戏还是anti-nim游戏
问是先手必胜还是必败
首先拿全是1的情况熟悉一下规则
如果全是1，那么无论有几堆，先手都是必胜的
因为如果有奇数个1，那么Alice直接拿掉魔力石子，然后选择不改变游戏，那么他还是赢的
如果有偶数个1，那么Alice直接拿掉魔力式子，然后选择改变游戏，于是他还是赢的。
然后回忆一下anti-nim的先手必胜条件（这里的SG不考虑多魔法石子的那一堆）
SG为0，且所有石子均为1
SG不为0，且存在一堆石子大于1
所以，如果不全是1，且SG为0的话，Alice是必输的，因为他取魔力石子后，仍然无法改变必输的情况
所以现在情况只有不全是1，且SG不为0
注意到这个时候任何一方如果直接取魔力石子，都是必败的
所以双方应该会保持SG不为0，然后进行对峙
首先考虑所以石子的数量不超过3
那么SG函数的值就只有3个，1,2,3
当SG为1或3的时候，肯定有一种取法使得SG为2
而SG为2的最终情况是2附加一个魔力石子，这种情况是必败的
所以当石子的数量不超过3时，SG=2先手必败，反之必胜
接下来考虑石子的数量超过3，也就是有4和4以上的数
那么SG函数的值可以分成1和超过1的那些情况
如果当前SG值为1，那么只能把它变成超过1的值，然而对手又可以把它变回到1
我们考虑假设只有1个超过3的数，那么这时候SG值肯定是大于3的
直接改变这个数，我们可以使得接下来的局面变成SG=2
也就是说，如果只有1个超过3的数，那么就是先手必胜
那么如果SG值为1，且我们知道存在超过3的数，那么超过3的数的数量必定至少有2个
也就是说，经过不断地对峙，原来SG值为1的话，现在SG值仍然为1
但是经过了很多减少，一定会达到这个局面
即SG值为1，且超过3的数量只有2个
当这2个其中的一个数减到4以下时，就变成了只有1个超过3的数
即SG->1->3以上->2（最终结果）
也就是说SG如果为1，必定会转化成2，那么SG=1就是必败局面，而其他情况是必胜局面
最后结论就是
如果有大于3的数，那么SG=1必败
如果没有，那么SG=2必败
（PS：题解的思路没有太明白，不知道是怎么想到右移1位然后分类的，然后莫名分类就分出来了orz）
#include#include #include #include #include #include #include #include #include #include #include using namespace std;class MagicNim { public: string findWinner(vector a) { sort(a.begin(), a.end()); int n = a.size(), sg = 0; for(int i = 0; i < n; i++) sg ^= a[i]; if(a[n-1] >= 4) return (sg == 1 ? "Bob" : "Alice"); else return (sg == 2 ? "Bob" : "Alice"); }};