【HDU 2176】 取(m堆)石子游戏
【题目链接】
http://acm.hdu.edu.cn/showproblem.php?pid=2176
【算法】
Nim博弈
当石子数异或和不为0时，先手必胜，否则先手必败
设石子异或和为S
如果S xor ai <= ai，那么，第一步就可以从第i堆石子中取走(S xor ai)个石子
【代码】
#include<bits/stdc++.h> using namespace std; #define MAXM 200010 int i,m,k,sum; int a[MAXM]; int main() { while (scanf("%d",&m) && m) { sum = 0; for (i = 1; i <= m; i++) { scanf("%d",&a[i]); sum ^= a[i]; } if (sum != 0) { printf("Yes "); for (i = 20; i >= 0; i--) { if (sum & (1 << i)) { k = i; break; } } for (i = 1; i <= m; i++) { if ((sum ^ a[i]) <= a[i]) printf("%d %d ",a[i],sum^a[i]); } } else printf("No "); } return 0; }