博弈–巴什博弈

0
10

  最近总是做到有关博弈之类的题目,突然想认真的了解一下,现在将我的了解总结如下,希望对看到的人有所帮助。同时也请多多支持哈~~

  巴什博弈是众多博弈种类中众多的一种,同时也是最简单的一种。它的基本模型是只有一堆物品,数量为n,两个人轮流从这堆物品中拿走x(1<=x<=m)个,拿走最后一个的人获胜。

  这里有两个基本的特点:一堆物品;两个人;拿走的数量处于一个区间内。

  下面我们对物品数量的组成有如下几种方式:

  1. 假设物品的数量有n=m+1个,那么先手一次最多拿走m个,假设先手拿走的数量处于[1,m],中,那么剩下的数量一定会处于[1,y](y处于[1,m]中),则后手一定可以一次性将剩下的物品拿走,先手必败。
  2. n=(m+1)*r个,同样的,先手一次最多拿走m个,假设先手拿走的数量num处于[1,m]中,那后手一定会拿走(m+1-num)个,是数量仍然满足n=(m+1)*r这个关系,这样进行若干轮后就会转换为第一种情况,此时先手必败。
  3. n=(m+1)*k+r。现在先手拿走的数量为r ,则剩下的数量为 n=(m+1)*k,注意此时是后手面临第二种情况,此时后手必败,先手必胜。

由此我们发现,谁面临的数量为(m+1)的整除倍,谁就必败。

入门题:

Brave Game

题意:模板题,题意就是两个人取石子,先去取光者获胜。

题解:巴什博弈

代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int n,a,b;
int main() {    
    cin>>n;
    while(n--){
        cin>>a>>b;
        if(a%(b+1)!=0){
            cout<<"first"<<endl;
        }else{
            cout<<"second"<<endl;
        }
    }
    return 0;
}

相同题目推荐:HDU-2188 HDU-2149

  

<

发布回复

请输入评论!
请输入你的名字