CSDN英雄会-第五届在线编程大赛月赛第三题：石子游戏（1）

题目详情
甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。
两人轮流按下列规则取走一些石子，游戏的规则如下：
1.每一步应取走至少一枚石子；
2.每一步只能从某一堆中取走部分或全部石子；
3.如果谁无法按规则取子，谁就是输家。
如果甲乙两人都采取最优的策略,甲先拿，请问,是甲必胜还是乙必胜.
输入格式：
多组数据，每组数据两行，第一行是一个整数N, 2<=N<=10000
下一行是N个正整数，代表每堆的石子数，石子数在32位整数内。
输出格式：
每组测试数据输出一行,如果甲存在必胜策略,输出”Win”,否则输出”Lost”
答题说明
输入样例
3
3 3 1
输出样例：
Win

这是一道很美妙的博弈论向的问题。（为博弈论中经典的模型：Nim游戏）

首先以递推的方式来看：
1、若仅仅存在一堆石子，那么甲是可以胜的（直接全拿走就好了），由于游戏中规定：甲乙两人都采取最优的策略。那么就说明在甲乙在这种前提下是必胜的。

2、若存在两堆石子，我们开始讨论：
对于[1,1]这样的情况，甲必败。
对于[n,1]这样的情况，甲可以将[n,1]变为[1,1]，于是在这种情况下甲是必胜的。
而对于[n,m]这样的情况，根据之前我们讨论的，甲需要避免的是：在甲取完后不能为[n,1]，那么如果是取为[n,2]呢？
假定我们采取这样的策略，同样地[n,2]依旧属于[n,m]类问题。采取这种策略必然会出现[2,2]这样的情况。而对于面对[2,2]这种情况的玩家来说，则是必败的。
以此类推[3,3]也是如此。继而可以得出，若开局为[n,n]类，则甲必败，反之，若开局为,[n,m]类，则甲必胜。（毕竟若m>n，则可以[n,m]=>[n,n]，则乙必败）

推演至n堆如何来做呢？
我们可以将每一大堆以相同的方式分为若干小堆。即将n个大堆，表示为n个k维向量，要求每一个向量的第i维与第j维（i不等于j）不相关（即对于任意的向量a，有a[i]=1 且 a[j]！=1,(i!=j)），每一维度值类型为Boolean类型，表示为该大堆在该维度上划分的小堆是否存在。而后，判断n个k维向量每一维存在的小堆个数，如果都为偶数，则甲必败（原因参照之前的讨论）
具体来说，对于一组样例8，11，2，14来说，这四个大堆可以表示为四个四维向量，即将他们划分为1个石子为一小堆、两个石子为一小堆、四个石子为一小堆、八个石子为一小堆的四种小堆。
08->[1,0,0,0]
11->[1,0,1,1]
02->[0,0,1,0]
14->[1,1,1,0]
由此可以得知，甲必胜。
样例为3，3，1 可以划分为二维向量
3->[1,1]
3->[1,1]
1->[0,1]
由此得知，甲必胜。

由于计算机中存储的整数为二进制，则可以将int型的石子数看作32维向量（题目中要求）且对于每一维来说，仅需要知道是否为偶数，那么可以通过位运算来解决。
于是我们需要设计出满足要求的布尔函数式：

Ａ　Ｂ　|　Ａｎｓ
——————————
０　０　|　０
０　１　|　１
１　０　|　１
０　０　|　０

于是可以推演出函数式：Ans=(~A & B) | (A & ~B)
其中，0代表该维度初始或经过计算后为偶数个小堆，反之为奇数个小堆。由于上述的划分，若向量表示第i个小堆存在，则仅存在1个第i个小堆，即为奇数个小堆。（这个运算很类似于不进位的加法运算）
而最终的结果是要看是否全部为偶数，则仅仅需判断累加器中的数是否为0

代码如下：

#include <stdio.h>
int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        int s = 0;
        while(n--){
            int temp;
            scanf("%d", &temp);
            s = (~s & temp) | (s & ~temp);
        }
        s?printf("Win\n"):printf("Lost\n");
    }
    return 0;
}