這一關(guān)我們上樓梯玩。。。

階梯博弈是這樣一個(gè)模型：有一個(gè)n層的臺(tái)階，每個(gè)臺(tái)階上都放有一定數(shù)量的石子。每次每個(gè)玩家可以選取某一層上任意數(shù)量的石子移動(dòng)到下一層，不能操作的人輸。

嗯這個(gè)問題看起來(lái)很復(fù)雜？我們先考慮簡(jiǎn)單的，顯然石子在第一層推下去的話相當(dāng)于是沒有了。那么我們假設(shè)所有的石子都在第一層，那這是一個(gè)先手必勝態(tài)。如果石子都在第二層呢？可以這樣考慮，先手每次把多少石頭推到第一層，后手就把先手推下來(lái)的石頭推下去，那這就是一個(gè)先手必?cái)B(tài)

那我們就會(huì)發(fā)現(xiàn)一個(gè)問題啦，偶數(shù)層的樓梯算是一個(gè)中轉(zhuǎn)，用來(lái)維護(hù)奇數(shù)層石子數(shù)量不變。只有奇數(shù)層的石子個(gè)數(shù)會(huì)對(duì)勝負(fù)產(chǎn)生影響，當(dāng)前玩家沒有必要維護(hù)偶數(shù)層的狀態(tài)。因?yàn)橛信紨?shù)層作為中轉(zhuǎn)，所以先手和后手都可以維護(hù)奇數(shù)層數(shù)目不變，即維護(hù)自己的必勝態(tài)。只考慮奇數(shù)層求出SG值即可。

1、

[HDU5996] dingyeye loves stone

題解：

這就是最簡(jiǎn)單的模型轉(zhuǎn)換啦，因?yàn)槊看沃荒馨旬?dāng)前節(jié)點(diǎn)的石子移動(dòng)到它的父節(jié)點(diǎn)上，這和臺(tái)階的模型是類似的。注意臺(tái)階的第一層還能往下推一次，但這里推到根節(jié)點(diǎn)就已經(jīng)GG了，所以根節(jié)點(diǎn)相當(dāng)于偶數(shù)層（因?yàn)樽饔迷谶@一層上也沒什么用嘛）

代碼：

#include <cstdio> #include <cstring> using namespace std; const int N=100005; int tot,nxt[N],point[N],v[N],k,a[N]; void addline(int x,int y){++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;} void dfs(int x,int D) {if (D) k^=a[x];for (int i=point[x];i;i=nxt[i]) dfs(v[i],!D); } int main() {int T,n,x;scanf("%d",&T);while (T--){k=0; tot=0; memset(point,0,sizeof(point));scanf("%d",&n);for (int i=2;i<=n;i++){scanf("%d",&x);x++;addline(x,i);}for (int i=1;i<=n;i++) scanf("%d",&a[i]);dfs(1,0);if (!k) printf("lose\n");else printf("win\n");} }

2、

[HDU4315] Climbing the Hill

題解：

我們只需要將中間的空格看成石子就可以解決這個(gè)問題，將編號(hào)為奇數(shù)的堆看成一個(gè)一個(gè)的區(qū)間，如果某一個(gè)人移動(dòng)了區(qū)間的左端點(diǎn)，那么下一個(gè)人就可以模仿它移動(dòng)區(qū)間的右端點(diǎn)相同的距離，這樣區(qū)間的長(zhǎng)度沒變，先手后手的順序也沒變。那么我們就可以說(shuō)，只有區(qū)間的長(zhǎng)度是有用的因素，與區(qū)間的位置無(wú)關(guān)。如果某一個(gè)人移動(dòng)了區(qū)間的右端點(diǎn)，就相當(dāng)于是從石子堆中取出了一些。
最后堆在一坨的自然是沒用了，這樣就等效成一個(gè)“最后一個(gè)區(qū)間是第一層”的階梯問題
所以我們的目標(biāo)狀態(tài)只是將所有的區(qū)間挪成空區(qū)間，沒有必要管區(qū)間的位置在哪里。并且，當(dāng)所有的區(qū)間都是空區(qū)間了之后，再將它移動(dòng)到山頂時(shí)，先手后手的順序還是沒有變化。
這個(gè)問題還要特別考慮一下國(guó)王，還要分類討論一下：顯然如果k=1的話先手必勝；k=2且第一個(gè)區(qū)間對(duì)這個(gè)問題有影響的時(shí)候（人數(shù)為奇數(shù)） ，先手后手都不希望把第一堆弄成0，因?yàn)檫@樣對(duì)手就會(huì)獲勝，所以第一堆的取值相當(dāng)于少了一個(gè)， SG1??

代碼：

#include <cstdio> using namespace std; int a[1005],n,k; int main() {while (~scanf("%d%d",&n,&k)){int ww=0;for (int i=1;i<=n;i++) scanf("%d",&a[i]);if (k==1) {printf("Alice\n");continue;}a[0]=-1;if (k==2 && n%2) a[0]=0;for (int i=n;i>=1;i-=2) ww^=a[i]-a[i-1]-1;if (!ww) printf("Bob\n");else printf("Alice\n");} }

3、

[HDU3389] Game

題解：

隨便打幾個(gè)表就可以看出所有的數(shù)推到1,3,4就推不下去了，其實(shí)題目也已經(jīng)告訴我們了，那兩個(gè)柿子相當(dāng)于告訴我們 (A+B)?%?6=3 ，推到134就是玩完了，不難發(fā)現(xiàn)那些%6=025的經(jīng)過(guò)奇數(shù)次就可以達(dá)到畫不動(dòng)的地步，但是%6=134的一定經(jīng)過(guò)偶數(shù)次推不動(dòng)了，我們的奇數(shù)層找到了？

代碼：

#include <cstdio> using namespace std; int a[10005]; int main() {int T,id=0,n;scanf("%d",&T);while (T--){int k=0;scanf("%d",&n);for (int i=1;i<=n;i++) {scanf("%d",&a[i]);if (i%6==0 || i%6==2 || i%6==5) k^=a[i];}if (k) printf("Case %d: Alice\n",++id);else printf("Case %d: Bob\n",++id);} }

4、

[BZOJ1115] [POI2009] 石子游戲Kam

題解：

我們可以通過(guò)模仿前面的行動(dòng)來(lái)維持兩堆石子的差不變，并且發(fā)現(xiàn)我們?nèi)∽咔耙粋€(gè)一部分石子，后面取的范圍會(huì)更大，而且我們?nèi)∽叨嗌俸竺婢湍茉黾佣嗌俜秶?#xff0c;總量不變！這是不是就像把前面的石子推到了后面？

那么后一堆-前一堆石子的數(shù)量就是我們等價(jià)的數(shù)量了，最后一堆只要在范圍內(nèi)，隨意減少都可以，【第一層推到最下面】

題目實(shí)際上就變?yōu)榱藦漠?dāng)前堆可以拿出一些石子放到下一堆里去，最后一堆可以直接往下推。典型階梯問題get？

代碼：

#include <cstdio> using namespace std; int a[1005],b[1005]; int main() {int T,n;scanf("%d",&T);while (T--){int k=0;scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=n;i++) b[i]=a[i]-a[i-1];for (int i=n;i>=1;i-=2) k^=b[i];if (k) printf("TAK\n");else printf("NIE\n");} }

總結(jié)

以上是生活随笔為你收集整理的博弈问题总集第三类----Staircase Nim的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。