算法之博弈问题

对于什么是博弈问题我们就不进行讲解了，我们直接讲理论和例题：

对于一个博弈问题，通常会有两种状态：必胜态和必败态

博弈问题也分为两种：平等和不平等博弈

下面我们先来看经典博弈模型：

一.巴什博弈

题目大体如下：

. - 力扣（LeetCode）

对于这类题，通常是一堆，两人每次可以取1~m个，问胜负？？？

//如果n%(m+1)==0,那么先手必败
if(n%(m+1)==0)
    //先手必败
else
    //先手必胜

利用公式，我们就可以解决该问题：

代码如下：

class Solution {
public:
    bool canWinNim(int n) 
    {
        if(n%4==0)
        return false;
        return true;
    }
};

二.威佐夫博弈

[SHOI2002] 取石子游戏|【模板】威佐夫博弈 - 洛谷

这就是一道典型的威佐夫问题，公式如下：

//若两堆物品的初始值为（x，y），且x<y(不满足swap)，则令z=y-x；

//记w=（int）[（（sqrt（5.0）+1.0）/2.0）*z ]；

//若w=x，则先手必败，否则先手必胜

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll a, b;
int main()
{
    cin >> a >> b;
    if (a > b)
        swap(a, b);
    int z = b - a;
    int w = (int)(((sqrt(5.0) + 1) / 2) * z);
    if (w == a)
        cout << "0" << endl;
    else
        cout << "1" << endl;
    return 0;
}

三.Nim游戏

【模板】Nim 游戏 - 洛谷

对于该类问题，解法如下：

//把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜
int x=0;
for(auto e:arr)
    x^=e;
if(x==0)
    //先手必败
else
    //先手必胜

所以该题解法如下：

#include <bits/stdc++.h>
using namespace std;
const int N=1e4;
int n,t,x,b;

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        int x=0;
        for(int i=1;i<=n;i++)
        {
            cin>>b;
            x^=b;
        }
        if(x==0)
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
    return 0;
}

四.斐波那契博弈

有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。

结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）

对于该类问题，我们需要先构造一个斐波那契数列，然后检查n是否斐波那契数

以上是对于博弈问题中的典型模型问题，但是实际上我们大部分的博弈问题都是可以用dp来解决的

最后，感谢大家的支持！！！