階梯博弈！！！下面闡述一下我對于階梯博弈的理解.. ? 首先是對階梯博弈的闡述...博弈在一列階梯上進行...每個階梯上放著自然數個點..兩個人進行階梯博弈...每一步則是將一個集體上的若干個點( >=1 )移到前面去..最后沒有點可以移動的人輸..


如這就是一個階梯博弈的初始狀態 2 1 3 2 4 ... 只能把后面的點往前面放...如何來分析這個問題呢...其實階梯博弈經過轉換 可以變為Nim.. 把所有奇數階梯看成N堆石子..做nim..把石子從奇數堆移動到偶數堆可以理解為拿走石子..就相當于幾個奇數堆的石子在做Nim..( 如所給樣例..2^3^4=5 不為零所以先手必敗)為什么可以這樣來轉化？ ? ?? 假設我們是先手...所給的階梯石子狀態的奇數堆做Nim先手能必勝...我就按照能贏的步驟將奇數堆的石子移動到偶數堆...如果對手也是移動奇數堆..我們繼續移動奇數堆..如果對手將偶數堆的石子移動到了奇數堆..那么我們緊接著將對手所移動的這么多石子從那個偶數堆移動到下面的奇數堆...兩次操作后...相當于偶數堆的石子向下移動了幾個..而奇數堆依然是原來的樣子...即為必勝的狀態...就算后手一直在移動偶數堆的石子到奇數堆..我們就一直跟著他將石子繼續往下移..保持奇數堆不變...如此做下去..我可以跟著后手把偶數堆的石子移動到0..然后你就不能移動這些石子了... 所以整個過程..將偶數堆移動到奇數堆不會影響奇數堆做Nim博弈的過程..整個過程可以抽象為奇數堆的Nim博弈... ? ?? 其他的情況...先手必輸的...類似推理...只要判斷奇數堆做Nim博弈的情況即可... ? ?? 為什么是只對奇數堆做Nim就可以...而不是 偶數堆 呢？...因為如果是對偶數堆做Nim...對手移動奇數堆的石子到偶數堆..我們跟著移動這些石子到下一個奇數堆...那么最后是對手把這些石子移動到了0..我們不能繼續跟著移動...就只能去 破壞原有的Nim而導致勝負關系的不確定 ...所以 只要對奇數堆做Nim 判斷即可知道勝負情況...
附加題目:

POJ 1704

【題意】

從左到右有一排石子，給出石子所在的位置。規定每個石子只能向左移動，且不能跨過前面的石子。最左邊的石子最多只能移動到1位置。每次選擇一個石子按規則向左移動，問先手是否能贏。

【分析】

我們把棋子按位置升序排列后，從后往前把他們兩兩綁定成一對。如果總個數是奇數，就把最前面一個和邊界（位置為0）綁定。

在同一對棋子中，如果對手移動前一個，你總能對后一個移動相同的步數，所以一對棋子的前一個和前一對棋子的后一個之間有多少個空位置對最終的結果是沒有影響的。

于是我們只需要考慮同一對的兩個棋子之間有多少空位。

這樣一來就成了N堆取石子游戲了.

HDU 4315
【題意】

有N個人爬山，山頂坐標為0，其他人的坐標按升序給出。不同的坐標只能容納一個人（山頂不限），Alice和Bob輪流選擇一個人讓他移動任意步，但不能越過前面那個人。現在有一個人是king（給出id），誰能將king移動到山頂就算贏。

【分析】

考慮King的情況和上述版本幾乎一致，只要把King當作普通人一樣處理即可。
除了兩種特殊情況：
1. 當King是第一個人時，Alice直接勝
2. 當King是第二個人且一共有奇數個人時，第一堆的大小需要減1。
因為如果king在奇數石子上,那么king前面的那一對石子k1,k2.
當對方把k1移到top時,我可以把k2移到top前的一個位置.
那么對于k2石子,對方如果碰了它,那么我肯定會把king移到top的.
所以k2也相當于是一顆廢子而已,不影響最終Nim的結果.

總結

以上是生活随笔為你收集整理的阶梯博弈（Staircase Nim）的全部內容，希望文章能夠幫你解決所遇到的問題。

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