尋找平衡狀態(tài)（也稱必敗態(tài)， 奇異局勢），（滿足：任意非平衡態(tài)經(jīng)過一次操作可以變?yōu)槠胶鈶B(tài)）

(一)巴什博奕(Bash Game):

只有一堆n個物品,兩個人輪流從這堆物品中取物,規(guī)定每次至少取一個,最多取m個.最后取光者得勝.

n = (m+1)r+s , (r為任意自然數(shù),s≤m), 即n%(m+1) != 0, 則先取者肯定獲勝

(二)威佐夫博奕(Wythoff Game):

有兩堆各若干個物品,兩個人輪流從某一堆或同時從兩堆中取同樣多的物品,規(guī)定每次至少取一個,多者不限,最后取光者得勝.

(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示奇異局勢

求法：

ak =[k(1+√5)/2], bk= ak + k (k=0,1,2,...,n 方括號表示取整函數(shù))

       判斷：

              Gold=(1+sqrt(5.0))/2.0；

1）假設(shè)（a，b）為第k種奇異局勢(k=0,1,2...) 那么k=b-a;

2）判斷其a==(int)(k*Gold),相等則為奇異局勢

（注：采用適當?shù)姆椒?/span>,可以將非奇異局勢變?yōu)槠娈惥謩?/span>.

假設(shè)面對的局勢是(a,b)

若 b = a,則同時從兩堆中取走 a 個物體,就變?yōu)榱似娈惥謩?/span>(0,0)；

1.       如果a = ak,

1.1   b > bk, 那么,取走b - bk個物體,即變?yōu)槠娈惥謩?/span>(ak, bk)；

1.2   b < bk 則同時從兩堆中拿走 ak – a[b – ak]個物體,變?yōu)槠娈惥謩?/span>( a[b – ak] , a[b – ak]+ b - ak)；

2         如果a = bk ,

2.1   b > ak ,則從第二堆中拿走多余的數(shù)量b – ak

2.2   b < ak ,則 若b = aj (j < k)  從第一堆中拿走多余的數(shù)量a– bj;  (a > bj)

若b = bj (j < k)  從第一堆中拿走多余的數(shù)量a– aj;  ( a > aj)

）

例題：pku 1067

(三)尼姆博奕(Nimm Game):

有n堆各若干個物品,兩個人輪流從某一堆取任意多的物品,規(guī)定每次至少取一個,多者不限,最后取光者得勝.

任何奇異局勢(a1, a2, … , an)都有a1(+)a2(+)…(+)an =0.  ( (+)為 按位與)

例題：pku 2234

例題：hdu 1730

例題：pku 1740

例題：pku 1704

例題：pku 1082 (大量分析… 結(jié)論很簡單。 也可以根據(jù)簡單的推論模擬實現(xiàn)。)