数据结构与算法:博弈类问题
前言
终于到博弈了,博弈问题在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时,偶数堆先手赢,奇数堆后手赢//当只有一堆大于