博弈--巴什博弈

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

　　巴什博弈是众多博弈种类中众多的一种，同时也是最简单的一种。它的基本模型是只有一堆物品，数量为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

 

　　

原文链接:https://www.cnblogs.com/blogxsc/p/12770657.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有