博弈训练——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;
}      

关于这题记录一次灵异事件：