Misere Nim

anti-nim游戏

他有一个结论：
1.所有的石子堆石子数都是1且sg=0
2.至少有一堆石子数不为1且sg!=0
满足上述条件中的一个先手就必胜！！！

首先，我们尝试证明(我的证明比较玄学。。。。。。)
首先对于第一个条件，是显而易见的。
石子数均为1，sg==0意味着有偶数个石子堆。sg!=0意味着有奇数个石子堆
那么答案自然就清楚了

那么对于第二个条件：
如果只有一堆的石子数>1的话，我们可以通过对这堆的石子进行操作
利用第一种条件获取胜利。
而如果有两堆或两堆以上的石子数>1的话呢？
根据sg定理，我们一定可以找到一个操作，使得在保持至少两堆石子数>1的情况下sg==0

因为后手接到的局面是sg==0的情况，那么他返回给先手的一定是sg!=0且又因为至少有两堆石子数>1
所以后说返回给先手的只有两种情况：
(1).至少有两堆石子数>1且sg!=0
(2).只有一堆石子数>1且sg!=0
其中(2)会使得先手必胜
而(1)则会使得博弈陷入递归，而递归的边缘就是(2)
因此先手必胜！！！！！！

代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int main() {
    int  T;scanf("%d", &T);
    int k;
    for (int tcase = 1;tcase <= T;++tcase) {
        scanf("%d", &k);int ans = 0;
        bool flag = true;
        for (int i = 1, stone;i <= k;++i) {
            scanf("%d", &stone);
            if (stone != 1)flag = false;
            ans ^= stone;
        }if ((flag && ans == 0) || (!flag && ans != 0))
            printf("Case %d: Alice\n", tcase);
        else printf("Case %d: Bob\n", tcase);
    }
}