题目详情 甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。 两人轮流按下列规则取走一些石子，游戏的规则如下： 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;}
因为有梦，所以勇敢出发，选择出发，便只顾风雨兼程。
