最近在数学这一块搞了蛮多题目，已经解决了数论基础，线性代数（只有矩阵，行列式待坑），组合数学中的一些简单问题。所以接下来不可避免的对博弈论这一哲学大坑开工。
当然，由于我很菜，所以也只能从最基础最容易的部分讲起了。
这次主要介绍两个基本模型：Bash Game&&Nim Game，还是比较经典的
下面开始讲
1.Bash Game
Bash Game(巴什博弈)是一种零基础的入门题目，它的基本模型大概是这样的：
一堆石子共n个，两人轮流从中取石子，规定每次至少取一个，最多取m个，最后取光者得胜。问两人博弈，他们都采用最聪明的策略，问最后谁可以必胜。
首先我们从小开始分析：
当m>=n时，先手可以一把抓完石子，这样先手必胜
当n=m+1时，先手无论怎么抓，都会留下1~m个石子，这样后手一把就可以抓完，这样先手必败
当m+1<n<2*(m+1)时，先手只要抓适当的石子就可以剩下m+1个石子，然后后手必输，那么先手必胜
当n=2*(m+1）时，后手可以采取这种策略，当先手抓x个时，后手就抓m+1-x个，这样就会把m+1的情况送给先手，那么先手必败
......
所以通过上面的分析我们很容易得出：当n%(m+1)==0时，先手必败；否则先手必胜
这个很简单吧，因为谁先面对k*(m+1)(k为正整数)这种局面就必定失败。因为一方可以每次让你们两个取得石子和为m+1导致另一方失败。
这个问题还有一些变形，比较经典的就是：把一个数从0开始不断增加，每次增加的范围都是1~k，谁先让数增加到n就Win||Lose
这个直接转化为Bash Game做一下即可
这里给几道例题&&CODE（以下例题都来自HDU）
1846
Bash博弈的板子题，直接上即可
CODE
#include<cstdio>
using namespace std;
int t,n,m;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
read(t);
while (t--)
{
read(n); read(m);
puts(n%(m+1)?"first":"second");
}
return 0;
}
2149
这就是那种变式的情况，我们转化一下在做转化个屁，至于输出方案的话特判一下即可
CODE
#include<cstdio>
using namespace std;
int n,m;
inline void write(int x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
int main()
{
register int i;
while (scanf("%d%d",&m,&n)!=EOF)
{
if (n>=m)
{
for (i=m;i<n;++i)
write(i),putchar(' '); write(n); putchar('\n');
} else
if (m%(n+1)) write(m%(n+1)),putchar('\n'); else puts("none");
}
return 0;
}
2138
同上，Bash Game直接上即可
CODE
#include<cstdio>
using namespace std;
int t,n,m;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
read(t);
while (t--)
{
read(n); read(m);
puts(n%(m+1)?"Grass":"Rabbit");
}
return 0;
}
4764
这道题就注意一下大于等于n你就输了，所以n要减一
CODE
#include<cstdio>
using namespace std;
int n,m;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (;;)
{
read(n); read(m);
if (!n&&!m) break;
puts((n-1)%(m+1)?"Tang":"Jiang");
}
return 0;
}
2.Nim Game
这其实是Bash Game的进化版，但是思维深度上了好几个台阶
首先我们看基本模型：
地上有n堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这n堆石子的数量，他想知道是否存在先手必胜的策略。
这是不是很复杂，首先我们考虑数据小的情况：
只有一堆石子时，除非没有石子，否则先手一把抓完即可
有两堆石子时，后手只需要跟随先手的动作即可
......（后面的根本分析不出来好吧）
但是在我们之前已经有大神成功证明了一个神奇的结论：
当n堆石子的数量异或和等于0时，先手必败，否则先手必胜
证明请移步至attack dalao's blog
很懵逼对吗其实我也是，那么让我们来感性理解一下（以下的说明仅为个人理解，几乎没有任何理论依据，请选择阅读）
首先由于全部都是0的时候就失败了，所以我们可以认为当它们的异或和为0就是必败态
这样我们先手是如果异或和为0那么就输了
如果不是呢，我们就可以通过一种猥琐的方法来获胜（就是上面讲的方法）
我们可以形象地认为它与Bash Game中先手先取得只剩下k*(m+1)然后通过让和始终为m+1来取胜
然后这就是神奇的Nim Game
这里有一道模板题Luogu P2197 nim游戏
由于就是裸的Nim Game，这里就直接上CODE了
#include<cstdio>
using namespace std;
int t,n,x,tot;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(t);
while (t--)
{
for (read(n),tot=0,i=1;i<=n;++i)
read(x),tot^=x;
puts(tot?"Yes":"No");
}
return 0;
}
当然这只是博弈论的入门，一些真正强力的东西如SG函数&&MINMAX等东西还是一脸懵逼