博弈訓練——nim與bash

本文主要記錄和nim博弈，bash game的相關問題。題目：

hdu 2188 悼念512汶川大地震遇難同胞——選拔志願者

hdu 2149 Public Sale

lightOJ 1253 Misere Nim

lightoj 1247 Matrix Game

hdu 1517 A Multiplication Game

hdu 2149 Public Sale（bash game）

​​http://acm.hdu.edu.cn/showproblem.php?pid=2188​​​

大意：二人捐款，每次捐款的錢數是1-m，誰先捐錢達到或大于n的人勝利

分析：

數量狀态	勝利者
1⟶m	grass
m+1	rabbit
m+2⟶2m+1	grass
2m+2	rabbit
2m+3⟶3m+2	grass
3m+3	rabbit

code:

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n%(m+1)==0) puts("Rabbit");
        else puts("Grass");
    }
    return 0;
}      

hdu 2149 Public Sale（bash game)

​​http://acm.hdu.edu.cn/showproblem.php?pid=2149​​​

大意：兩個人報價競争一塊土地，每一次出錢有一個限度。求解如果第一個人勝利，他需要在第一次出的錢。

分析：如果第一個人能夠保證差價剩下k*（m+1），那麼最後的競價次數一定能控制剛好等于k。

code:

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int n,m;
    while(cin>>n>>m){
        if(n%(m+1)==0) puts("none");
        else {
            if(n<=m) {
                for(int i=n;i<m;i++) printf("%d ",i);
                printf("%d\n",m);
            }
            else {
                int res=n%(m+1);
                printf("%d\n",res);
            }
        }
    }
    return 0;
}      

lightOJ 1253 Misere Nim（轉化nim博弈）

​​http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1253​​​

大意：和普通的nim遊戲相比這裡是先拿完物品的人輸。單純的讨論必然思考各種複雜的情況，現在我們轉化它成一般性的nim遊戲。

ｎim game 誰先拿完誰就赢　最後的權利在我的手上，隻要ｎ>1，我就能剩下１，保證我赢。

如果全是１，那就依據單純的奇偶性判斷，奇數赢，偶數輸（全部針對先手而言）

code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;  // vim game 誰先拿完誰就赢　最後的權利在我的手上，隻要ｎ>1，我就能剩下１
int main()
{
    //freopen("cin.txt","r",stdin);
    int t,n,ca=1,a;
    cin>>t;
    while(t--){
        scanf("%d",&n);
        int one=0,ans=0;
        for(int i=0;i<n;i++) {
            scanf("%d",&a);
            ans=ans^a;
            if(a==1)one++;
        }
        if(one==n) {  // 如果全是１，那就依據單純的奇偶性判斷，奇數赢，偶數輸
            ans=(n&1)?0:1;
        }
        if(ans==0) printf("Case %d: Bob\n",ca++);
        else printf("Case %d: Alice\n",ca++);
    }
    return 0;
}      

lightoj 1247 Matrix Game（nim博弈）

​​http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1247​​​

大意：在一個n×m的矩陣中每個格子有一些石子。兩人玩遊戲，每一個人一次可以選擇一行，任意取不少于１個石子，取完最後一個石子的人赢。

分析：nim遊戲的簡單變形，隻要将一行變成一個數字就行。

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
LL s[60];
int main(){
    //freopen("cin.txt","r",stdin);
    int t,a,ca=1;
    int n,m;
    cin>>t;
    while(t--){
        scanf("%d%d",&n,&m);
    memset(s,0,sizeof(s));
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
           scanf("%d",&a);
           s[i]+=a;
        }
        ans=ans^s[i];
    }
        if(ans) printf("Case %d: Alice\n",ca++);
    else printf("Case %d: Bob\n",ca++);
    }
    return 0;
}      

hdu 1517 A Multiplication Game（規律）

​​http://acm.hdu.edu.cn/showproblem.php?pid=1517​​​

大意：兩個人玩遊戲，數字初值是1，現在輪流乘上一個數字，乘數是2—9的範圍，誰做乘法後結果大于等于n誰就是赢家。

範圍	赢家
2–9	S
9+1⟶	O
2*9+1⟶2*9*9	S
2*9*9+1⟶2*9*9*2	O
2*9*9*2+1⟶2*9*9*2*9	S

對于一個給定的數字n可以直接由上表确定輸家和赢家。用浮點數！

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    //freopen("cin.txt","r",stdin);
    double n;
    while(cin>>n){
        while(n>18){
            n/=18;
        }
        if(n<=9) puts("Stan wins.");
        else puts("Ollie wins.");
    }
    return 0;
}      

關于這題記錄一次靈異事件：