学步园

  这个游戏是说，有m堆硬币，两个人分别来取，每人每次能从任意一堆中去任意多的硬币（但只能从一堆中取），现在告诉你具体每堆的数量，然后让你判断先取者胜，还是后取者胜。

解：

设每堆的数量为：a1, a2, a3,.....am;

由于每一个整数都能表示成二进制数，那么将这些数表示成二进制：

a1 = b(m-1)b(m-2)b(m-3)....b0;

a2 = c(m-1)c(m-2)c(m-3)....c0;

..........（位数不够的用零补齐）

现在设 ：   

 若  b(m-1) + c(m-1) + ...... == 偶数， 则称第 j 位是平衡的，否则是不平衡的。若在某状态下，所有位都是平衡的，则该状态为平衡状态，否则为非平衡状态。

现在，该问题的一个解释：初始状态为平衡状态时，后取者胜，否则先取者胜。

原因：

当初始状态状态为非平衡状态时，假设最大非平衡状态位为第 j 位，那么先取者一定能从第 j 位是1的某一堆中去一定数量的硬币使状态变为平衡状态。现在后取者无论怎么取都得给先取者留下不平衡的状态......然后先取者再将其变平衡即可，这样往复循环 先取者最终将状态变为 所有都为零的平衡状态。

当初始状态为平衡状态，调换顺序即可。

该游戏在HDOJ上有一题http://acm.hdu.edu.cn/showproblem.php?pid=2176

代码如下：

#include <iostream>
using namespace std;

int main(){
	int a[200000], n, t;

	while( cin >> n, n ){
		t = 0;
		for( int i = 0; i < n; i++ ){
			cin >> a[i];
			t ^= a[i];
		}

		if( t == 0 ){
			cout << "No" << endl;
		}else{
			cout << "Yes" << endl;
			for( int i = 0; i < n; i++ ){
				if( ( t ^ a[i] ) < a[i] ){
					cout << a[i] << " " << ( t ^ a[i] ) << endl;
				}
			}
		}
	}
}