数据结构与算法：博弈类问题

前言

终于到博弈了，博弈问题在cf里还挺常见的。

一、博弈类问题

1.内容

博弈类问题分为公平组合游戏、非公平组合游戏（棋类）和反常游戏。反常游戏可以看作公平组合游戏的变形，所以我们只需要研究公平组合游戏（ICG）即可。

在博弈类问题里，两玩家都只会做出最优的选择。而且博弈类问题没有随机成分，当局面确定时，结果必然是注定的。

2.公平组合游戏（ICG）

公平组合游戏有四个条件：两个玩家轮流行动且行动方式一致、两个玩家对状况完全了解、游戏一定会在有限步内分出胜负和游戏必然以某玩家无法行动结束。

二、经典博弈

1.巴什博弈

（1）内容

一共有n颗石子，两个人轮流拿，每次可以拿1~m颗石子，拿到最后一颗石子的人获胜。

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//结论：只要n不等于m+1的整倍，则必然先手赢//动态规划验证
int MAXN=1001;
vector<vector<string>>dp(MAXN,vector<string>(MAXN));
string bash1(int n,int m)
{if(n==0){return "后手";}if(dp[n][m]!=""){return dp[n][m];}string ans="后手";for(int p=1;p<=m;p++){if(bash1(n-p,m)=="后手"){ans="先手";break;}}dp[n][m]=ans;return ans;
}//正解
string bash2(int n,int m)
{return n%(m+1)!=0?"先手":"后手";
}void test()
{srand(time(0));int testTime=5000;int V=500;cout<<"Start"<<endl;for(int i=1;i<=testTime;i++){int n=rand()%V;int m=rand()%V+1;string ans1=bash1(n,m);string ans2=bash2(n,m);if(ans1!=ans2){cout<<"Wrong"<<endl;}}cout<<"Over"<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;// while(t--)// {//     solve();    // }test();return 0;
}

观察可以发现，只要n初始不为m+1的整数倍，则必然是先手赢。

举个例子，当n等于4，m等于3时，此时先手不管拿几个，后手都可以一次拿完，那么先手是必输的。当n等于5，m依然为3时，此时先手可以先拿一个，然后让后手面对n等于4的情况，那么此时先手就是必胜的。所以推广到一般情况，只要初始n不等于m+1的整数倍，则先手必然可以每次让后手面对等于m+1整数倍的情况，则先手必胜。

（2）扩展——Roy&October之取石子

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int n;cin>>n;//只要n不是6的整数倍，先手赢cout<<(n%6!=0?"October wins!":"Roy wins!")<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

从n等于1开始举例并观察规律，可以发现，直到当n等于6时先手才是必输的。而当n处于7到11时，先手总可以让后手面对n等于6的状态，直到n等于12时先手必输。所以只要n不等于6的整数倍，先手就是必胜的。

2.尼姆博弈——Nim 游戏

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//异或和不等于0，先手赢void solve()
{int n;cin>>n;int a;int eor=0;for(int i=0;i<n;i++){cin>>a;eor^=a;}   cout<<(eor!=0?"Yes":"No")<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

尼姆博弈这个结论完全是通过后面的sg定理推出来的，纯靠找规律基本不太可能想到……

规律就是只要所有堆的石头数的异或和不等于0，那先手就是必胜的。

硬推这个原理的话就是，若异或和不等于0，则必存在至少一位上有奇数个1，这样异或起来才会导致该位的结果为1。那么必然存在一种拿法使得先手可以在所有1的个数为奇数的位上使1的个数变为偶数，从而让后手面对异或和等于0的必败态。

3.反尼姆博弈——小约翰的游戏

这就是一个反常游戏了。

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//当每堆都是1时，偶数堆先手赢，奇数堆后手赢//当只有一堆大于