博弈--巴什博弈

　　最近總是做到有關博弈之類的題目，突然想認真的瞭解一下，現在將我的瞭解總結如下，希望對看到的人有所幫助。同時也請多多支持哈~~

　　巴什博弈是眾多博弈種類中眾多的一種，同時也是最簡單的一種。它的基本模型是只有一堆物品，數量為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