LightOJ 1253 Misere Nim【Nim博弈变形】

题意：

有k堆石子，Alice先手，每个人每次可以任选一堆石子取$1$ ~ $a_i$个石子。取到最后一个石子的输。

思路：

先考虑一种特殊情况，就是所有石子都是1的时候，这种情况下谁赢谁输已经确定了。

剩下的情况，如果改为取到最后一个石子的获胜的情况的话，就是典型的尼姆博弈了。然而这里很巧的是Nim博弈的结论对这题同样适用，因为Nim博弈的获胜方总能将一个石子留给另外一个人。

MyCode：

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

int t, n, tem, res, flag;
int main()
{
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        flag = res = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &tem);
            res ^= tem;
            if(tem != 1)    flag = 1;
        }
        printf("Case %d: ", cas);
        if(flag)
            puts(res ? "Alice" : "Bob");
        else
            puts((n & 1) ? "Bob" : "Alice");
    }
    return 0;
}