pku 1740 A New Stone Game（博弈，感性）

博弈类问题的关键，就是寻找平衡状态。
这题的平衡状态是什么？石头堆的数量是成对出现的，也就是说后取者总可以模仿先取者。

逐一分析：
剩余1堆石头：先取者全部拿走，胜利。
剩余2堆石头：假设两堆石头的数量相等，均为m。对于(m,m)，先取者没办法一次将两堆石头拿走，则后取者总可以模仿先取者的动作，只需换一下操作对象，使两堆石头变成(n,n)。最后肯定有某一次先取者操作后石头只剩下一堆，这时后取者将剩下的一堆全部拿走，胜利。
也就说，对于(m,m)，后取者必胜。
如果两堆石头不相等，(m,n)，则先取者把多的那一堆拿走一些，使两堆相等(n,n)。
也就说，对于(m,n)，先取者必胜。
剩余3堆石头：(x,y,z)其中(x<=y<=z)，先取者可以把z分(y-x)到x上，剩下的全部拿走，于是局面变成了(y,y,0)。也即是说对于3堆石头，先取者必胜。
对于4堆石头：如果(m,m,n,n)，这样和两堆石头的(m,m)局面是类似的，先取者必败，后取者必胜。但如果不是这样的情况，(a,b,c,d)其中(a<=b<=c<=d)，先取者操作最后一堆石头，总可以使局面变成(a,c,c,a)。这样就把必败局留给了后取者，也就是说这种情况先取者必胜。
对于n堆石头，分析和前面类似。。。。。

总的来说，对于n堆石头：
如果n是奇数，先取者必胜。
如果n是偶数，石头堆排序后可以写成(a,a,b,b,c,c,d,d,....)则先取者必败，否则先取者必胜。

#include <algorithm> #include <iostream> using namespace std; int n,num[10]; int check() { if(n%2) return 1; sort(num,num+n); for(int i=0;i<n;i+=2) if(num[i]!=num[i+1]) return 1; return 0; } int main() { while(scanf("%d",&n)&&n) { for(int i=0;i<n;i++) scanf("%d",&num[i]); printf("%d/n",check()); } return 0; }