來源：http://blog.csdn.net/jqandjq/archive/2009/02/27/3943422.aspx

有若干堆各若干個物品，兩個人輪流從某一堆取任意多的物品，規定每次至少取一個，多者不限，最后取光者得勝。

相關的經典例題：http://acm.hdu.edu.cn/showproblem.php?pid=2176

這種情況最有意思，它與二進制有密切關系，我們用（a，b，c）表示某種局勢，首先（0，0，0）顯然是奇異局勢，無論誰面對奇異局勢，都必然失敗。第二種奇異局勢是（0，n，n），只要與對手拿走一樣多的物品，最后都將導致（0，0，0）。仔細分析一下，（1，2，3）也是奇異局勢，無論對手如何拿，接下來都可以變為（0，n，n）的情形。

計算機算法里面有一種叫做按位模2加，也叫做異或的運算，我們用符號（+）表示這種運算。這種運算和一般加法不同的一點是1+1=0。先看（1，2，3）的按位模2加的結果：

1 =二進制01

2 =二進制10

3 =二進制11 （+）

———————

0 =二進制00 （注意不進位）

對于奇異局勢（0，n，n）也一樣，結果也是0。

任何奇異局勢（a，b，c）都有a（+）b（+）c =0。

如果我們面對的是一個非奇異局勢（a，b，c），要如何變為奇異局勢呢？假設 a < b< c,我們只要將 c 變為 a（+）b,即可,因為有如下的運算結果: a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要將c 變為a（+）b，只要從 c中減去 c-（a（+）b）即可。

?

?

代碼 1 #include <iostream>
2 ?using namespace std;
3
4 ?int main()
5 {
6 int a[200005];
7 int n, i, j, t, p, flag;
8
9 while (scanf("%d", &n) != EOF && n)
10 {
11 p = flag = 0;
12 for (i = 0; i < n; i++)
13 scanf("%d", a + i), p ^= a[i];
14 for (i = 0; i < n; i++)
15 {
16 t = p ^ a[i]; //t=a[0](+)a[1]...a[n-1] 異或
17 ? if (t < a[i])
18 {
19 if (!flag) puts("Yes");
20 printf("%d %d\n", a[i], t);
21 flag = 1;
22 }
23 }
24 if (!flag) puts("No");
25 }
26 }

?

?

轉載于:https://www.cnblogs.com/touchsunlight/archive/2010/03/20/1690401.html

總結

以上是生活随笔為你收集整理的HDOJ 2176 取石子游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。