巴什博弈：

只有一堆n個(gè)物品，兩個(gè)人輪流從這堆物品中取除，每次取的個(gè)數(shù)為[1,m](至少去一個(gè)，最多取m個(gè))，最后取完者獲勝

特征：

物品只有一堆，簡(jiǎn)單變形：

要么在范圍內(nèi)不規(guī)定個(gè)數(shù)，要么規(guī)定只能取幾個(gè)?

分析：

1.如果n<=m,那么先者一定贏?

2.如果n=m+1,那么由于一次最多取m個(gè)，無(wú)論先取者拿走多少個(gè)，后者一定能夠一次拿走所有物品，后者取勝?

3.因此，我們發(fā)現(xiàn)了如何取勝的方法：
如果n=(m+1)*r+s;(r為任意自然數(shù)，s<=m),那么先取者拿走s個(gè)物品，后取者拿走k(k<=m)個(gè)物品，先取者再拿走（m+1-k）個(gè)物品，結(jié)果剩下（m+1）*（r-1）個(gè)物品，那么先取者一定獲勝

4.要保持給對(duì)手留下（m+1）的倍數(shù)個(gè)物品，只要n%(m+1)!=0,先取者一定獲勝

?例題：

NYOJ２３取石子（一）

//hdu2149 巴什博弈 #include<bits/stdc++.h> using namespace std;int main() {ios::sync_with_stdio(false);int n,m,t;cin>>t;while(t--){cin>>n>>m;if(n%(m+1)!=0)printf("Win\n");elseprintf("Lose\n");}return 0;}

HDU２１４９????Public Sale

//hdu2149 巴什博弈 #include<bits/stdc++.h> using namespace std;int main() {ios::sync_with_stdio(false);int n,m;while(cin>>n>>m){if(n<=m){for(int i=n;i<m;i++)printf("%d ",i);printf("%d\n",m);}else{if(n%(m+1)==0)printf("none\n");else{bool first=1;//控制輸出格式 for(int s=1;s<=m;s++){if((n-s)%(m+1)==0){if(first){//如果是第一個(gè)元素 printf("%d",s);first=0;//已輸出第一個(gè)元素 } elseprintf(" %d");//非第一個(gè)元素，前面右一個(gè)空格 }}printf("\n");}}}return 0;}

優(yōu)化之后的代碼：

1.若n>m,先取者必勝
2.若n%(m+1)!=0，那么第一個(gè)取的數(shù)就是n%(m+1);

留給對(duì)手的就是m+1的倍數(shù)?

#include<iostream> using namespace std; int main() { int n;//成本 int m;//最大加價(jià) while(scanf("%d%d",&n,&m)!=EOF){ if(n%(m+1)==0) cout<<"none";else{ if(n%(m+1)) cout<<n%(m+1); //直接取余數(shù) if(m>=n){ for(int i=n+1;i<=m;i++)cout<<" "<<i;} }cout<<endl;}return 0; }

Java?

import java.util.*; import java.math.*;public class Main{static int MAXN=(int)(2e5+10);public static void main(String[] args) {Scanner cin=new Scanner(System.in);while(cin.hasNext()) {int m=cin.nextInt();int n=cin.nextInt();if(m<=n) {for(int i=m;i<=n;i++) {System.out.print(i);if(i==n)System.out.println();elseSystem.out.print(" ");}continue;}if(m%(n+1)==0)System.out.println("none");else {int x=m%(n+1);System.out.println(x);}}cin.close();} }

HDU1847 巴什博弈
尋找必?cái)顟B(tài)，若n%3=0，則cici贏，否則kiki贏
枚舉前面幾個(gè)數(shù)，找規(guī)律

分析：

1.若留給cici的是3，那么cici只能取1個(gè)或者2個(gè)
所以下一次Kiki取后必贏
2.若是給Cici留下的是3的倍數(shù)，假設(shè)為3n(n=1,2,3,..)，
那么無(wú)論Cici取什么數(shù)，剩余的數(shù)一定可以寫(xiě)成3m+1或者3m+2(m<n)的形式，
那么只要Kiki再取的時(shí)候留給Cici的仍然是3的倍數(shù)的話，就必勝了?

#include<bits/stdc++.h> using namespace std;int main() {ios::sync_with_stdio(false);int n;while(cin>>n){if(n%3==0)cout<<"Cici\n";else cout<<"Kiki\n";} return 0;}

HDU2188?

import java.util.*; import java.math.*;public class Main{static int MAXN=(int)(2e5+10);public static void main(String[] args) {Scanner cin=new Scanner(System.in);int T=cin.nextInt();while((T--)!=0) {int n=cin.nextInt();int m=cin.nextInt();if(n<=m) {System.out.println("Grass");continue;}if(n%(m+1)==0) {System.out.println("Rabbit");}else {System.out.println("Grass");}}cin.close();} }

HDU 2897 巴什博弈變形

每行有三個(gè)數(shù)字n，p，q，表示一堆硬幣一共有n枚，從這個(gè)硬幣堆里取硬幣，一次最少取p枚，最多q枚，如果剩下少于p枚就要一次取完。兩人輪流取，直到堆里的硬幣取完，最后一次取硬幣的算輸。對(duì)于每一行的三個(gè)數(shù)字，給出先取的人是否有必勝策略，如果有回答WIN，否則回答LOST。

Input

不超過(guò)100000行，每行三個(gè)正整數(shù)n，p，q。

Output

對(duì)應(yīng)每行輸入，按前面介紹的游戲規(guī)則，判斷先取者是否有必勝策略。輸出WIN或者LOST。

Sample Input

7 2 4

6 2 4

Sample Output

LOST

WIN

分析：

假設(shè)先取者為A，后取者為B，初始狀態(tài)下有石子n個(gè)，除最后一次外，其他每次取得石子個(gè)數(shù)必須在[p，q]之間。?

1）：若當(dāng)前石子共有n = （p+q） * r個(gè)，則A必勝；

必勝策略為：A第一次取q個(gè)，以后每次若B取K個(gè)，A取（p+q-k）個(gè)，如此下去；最后必剩下p個(gè)給B，所以A必勝。?

2）若n = （p+q）* r + left個(gè)（1 <= left <= p）B必勝；

必勝策略為：每次取石子活動(dòng)中，若A取k個(gè)，則B去（p+q-k）個(gè)，那么最后剩下left個(gè)給A，此時(shí)left <= p，所以A只能一次去完，B勝。?

3）若n = （p+q） * r + left個(gè)（p < left <= q），則A必勝；

必勝策略為：A第一次取t（1 <= left – t < = p）個(gè)，以后每次B取k個(gè)，則A取（p+q-k）個(gè)，那么最后留下1 <= left – t <= p給B，則A勝。

（也就相當(dāng)于當(dāng)A取得時(shí)候，他可以把當(dāng)前局勢(shì)變?yōu)榈?種的，即讓B面對(duì)必?cái)B(tài)，這時(shí)候的原理和第2種就一樣了）

import java.util.*; import java.math.*;public class Main{static int MAXN=(int)(2e5+10);public static void main(String[] args) {Scanner cin=new Scanner(System.in);while(cin.hasNext()) {int n=cin.nextInt();int p=cin.nextInt();int q=cin.nextInt();int left=n%(p+q);if(left==0)System.out.println("WIN");else if(left<=p)System.out.println("LOST");else System.out.println("WIN");}cin.close();} }

打表代碼

#include <cstdio> #include <cstring> #include <algorithm> #include<iostream> using namespace std; const int maxn=2e5+10; int sg[maxn]; int vis[maxn]; void SG(int n,int p,int q) {int i,j;memset(sg,0,sizeof(sg));for(i=p+1; i<=n; ++i){memset(vis,0,sizeof(vis));for(j=p; j<=q; ++j)vis[sg[i-j]]=1;//標(biāo)記最小的不屬于這個(gè)集合的非負(fù)整數(shù)for(j=0; j<n; ++j)if(!vis[j]){sg[i]=j;break;}}for(i=0; i<n; i++)cout<<sg[i]<<endl; } int main(){int n,p,q;while(scanf("%d%d%d",&n,&p,&q)!=EOF){SG(n,p,q);} }

?

總結(jié)

以上是生活随笔為你收集整理的巴什博弈例题：NYOJ23；HDU：2149，1847，2897，2188的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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