?ACM博客_kuangbin

博弈-翻硬幣游戲

hihoCoder

1172 : 博弈游戲·Nim游戲·二

時間限制:10000ms

單點時限:1000ms

內(nèi)存限制:256MB

描述

Alice和Bob這一次準(zhǔn)備玩一個關(guān)于硬幣的游戲：
N枚硬幣排成一列，有的正面朝上，有的背面朝上，從左到右依次編號為1..N。現(xiàn)在兩人輪流翻硬幣，每次只能將一枚正面朝上的硬幣翻過來，并且可以隨自己的意愿，在一枚硬幣翻轉(zhuǎn)后決定要不要將該硬幣左邊的任意一枚硬幣也翻一次(正面翻到背面或背面翻到正面)。翻最后一枚正面向上的硬幣的人獲勝。同樣的，這次游戲里面Alice仍然先手，兩人均采取最優(yōu)的策略，對于給定的初始局面，Alice會獲勝還是Bob會獲勝？

提示：Turning Turtles

輸入

第1行：1個正整數(shù)N，表示硬幣數(shù)量。1≤N≤10,000
第2行：1個字符串，第i個字符表示編號為i的硬幣狀態(tài)，’H’表示正面朝上，’T’表示背面朝上。

輸出

第1行：1個字符串，若Alice能夠獲勝輸出"Alice"，否則輸出"Bob"

樣例輸入

8 HHTHTTHT

樣例輸出

Bob

Turning Turtles

這個游戲叫做Turning Turtles，它的本質(zhì)就是Nim游戲。那么它到底是如何轉(zhuǎn)化為Nim游戲的呢？讓我們一步一步來分析。

首先，我們先將局面分解一下，每一次我們只考慮一枚硬幣。
不妨設(shè)所有硬幣全部背面朝上的局面為局面0
假設(shè)現(xiàn)在N枚硬幣，只有第1枚是正面朝上的。該局面只能轉(zhuǎn)化為全部硬幣背面朝上的局面。我們假定該局面為 局面1，則局面1可以轉(zhuǎn)化為局面0。
假設(shè)只有第2枚是正面朝上的。該局面可以轉(zhuǎn)化為：只有硬幣1正面朝上；全部硬幣背面朝上。我們假定該局面為 局面2，局面2可以轉(zhuǎn)化為局面1和局面0。
同理我們可以推定，第i枚硬幣正面朝上的局面為局面i，局面i可以轉(zhuǎn)化為局面0..i-1。

現(xiàn)在，我們考慮把給定的局面拆成單個硬幣的局面集合

比如給定了{(lán)HHTHTTHT}，其中H表示正面朝上，T表示背面朝上。那么就是當(dāng)前局面={局面1，局面2，局面4，局面7}。每一次我們可以改變其中個一個局面，當(dāng)出現(xiàn)局面0時就從集合中刪去。
這樣一看是不是就變成了Nim游戲了？然而事實并沒有那么簡單。

進一步分析，若同時存在i,j(j<i)兩枚硬幣正面朝上。我們將這個局面拆成2個單一的局面：即局面i和局面j。
在反轉(zhuǎn)i的時候我們考慮從局面i轉(zhuǎn)移到局面j，那么我們會有兩個局面j。
表示第j枚被反轉(zhuǎn)了2次，也就是回到了背面朝上的狀態(tài)。
那么我們得到這個游戲一個性質(zhì)：當(dāng)出現(xiàn)兩個同樣的局面時，等價于這兩個局面合并變成了局面0。

這種情況在Nim游戲中是沒有的，那么它會對Nim游戲的狀態(tài)造成影響么？
我們想一想，在Nim游戲中，如果出現(xiàn)兩個數(shù)量相同的堆時，比如A[i]=A[j]。在計算Nim游戲狀態(tài)時我們采用的xor操作，xor有交換律和結(jié)合律。則我們可以變成：
(A[i] xor A[j]) xor Other
因為A[i] = A[j]，所以A[i] xor A[j] = 0。上式實際就是：
0 xor Other
也就是說在原Nim游戲中，若出現(xiàn)了兩個數(shù)量相同的堆時，實際上這兩堆已經(jīng)不對總局面造成影響了，也就可以認(rèn)為這兩對合并為了一個數(shù)量為0的堆。

到此，我們可以發(fā)現(xiàn)這個硬幣游戲完全滿足Nim游戲的規(guī)則，其解答也滿足Nim游戲的性質(zhì)，這題也就很簡單的轉(zhuǎn)化為了普通的Nim游戲。在實際的博弈游戲中會發(fā)現(xiàn)很多都是可以轉(zhuǎn)化為Nim游戲模型。如何正確的建立模型和轉(zhuǎn)化游戲模型也就是解決博弈游戲一個很重要的手段。

比如Nimble游戲：
游戲開始時有許多硬幣任意分布在樓梯上，共N階樓梯從地面由下向上編號為0到N。游戲者在每次操作時可以將任意一枚硬幣向下移動，直至地面。游戲者輪流操作，將最后一枚硬幣移至地面(即第0階)的人獲勝。在雙方都采取最優(yōu)策略的情況下，對于給定的初始局面，問先手必勝還是先手必敗。
每一枚硬幣仍然對應(yīng)了一個石子堆，向下移動就等價于從石子堆里面取出石子。

同樣的例子還有很多，有些游戲甚至需要做好幾次轉(zhuǎn)換才能移動到Nim游戲模型，在之后我們就會見到。

import java.util.*; import java.math.*;public class Main{static int MAXN=(int)(500+10);public static void main(String[] args) {Scanner cin=new Scanner(System.in);while(cin.hasNext()) {int n=cin.nextInt();String str=cin.next();int len=str.length();int ret=0;for(int i=0;i<len;i++) {if(str.charAt(i)=='H')ret^=(i+1);}if(ret==0)System.out.println("Bob");elseSystem.out.println("Alice");}cin.close();} }

HDU3537

題意：

有一排硬幣，告訴 你n個正面朝上的硬幣的位置，你可以選擇任意位置的1~3個硬幣翻轉(zhuǎn)一下，但是問你先手是否會輸。

打表找規(guī)律

#include<stdio.h> #include<string.h> //統(tǒng)計x的二進制表示中1的個數(shù) static int countOne(int x) {int ans=0;while(x!=0) {if((x&1)!=0) ans++;x=x>>1;}return ans; } int vis[1007],sg[1007]; int main() {for(int i=1;i<100;i++){memset(vis,0,sizeof(vis));vis[0]=1;//翻一枚for(int j=0;j<i;j++)vis[sg[j]]=1;//翻兩枚for(int j=0;j<i;j++)for(int k=0;k<j;k++)vis[sg[j]^sg[k]]=1;//翻三枚for(int k=0;;k++)if(!vis[k]){sg[i]=k;break;}printf("%d,%d,%d\n",i-1,sg[i],countOne(i-1));} }

規(guī)律：

若X的二進制表示里1的個數(shù)為奇數(shù)，則SG[x]=2*x；

若X的二進制表示里1的個數(shù)為偶數(shù)，則SG[x]=2*x+1；

最后N個X的SG值異或為0，先手必敗；

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<math.h> #include<set> using namespace std; const int maxn = 1e6+10; typedef long long LL; //統(tǒng)計x的二進制表示中1的個數(shù) static int countOne(int x) {int ans=0;while(x!=0) {if((x&1)!=0) ans++;x=x>>1;}return ans; } //計算x的SG值 static int SG(int x) {int one=countOne(x);if(one%2==1)return x<<1;//sg=2*x；return x<<1|1;//sg=2*x+1 } int main() {int n;while(scanf("%d",&n)!=EOF){set<int>s;//自動去重for(int i=0;i<n;i++){int x;scanf("%d",&x);s.insert(x);}int ret=0;set<int>::iterator it;for(it=s.begin();it!=s.end();it++){//printf("%d\n",*it);ret^=SG(*it);}if(ret==0)printf("Yes\n");elseprintf("No\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的浅谈 翻硬币游戏【Nim博弈】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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