写在之前

我打算发一个大篇的博弈论

这是一个大纲

这其中也存在来自多方大佬的转载

希望可以解答一些各位心中的疑惑

透彻博弈论

cdy:@xkj 博弈论是个啥？？？

xkj:@cdy 学科技的【科普时间】

我们接下来会讲些什么

1.四大经典博弈

2.博弈树(构造状态图)

3.SG函数

4.一些杂讲(这块就是比较乱)

~~顺序是乱的~~

博弈树(博弈流程图)

这玩意就跟dfs树一样状态量一般很大

但是同样跟dfs树一样可以玄学剪枝

可以针对一些比较简单的博弈

我们就先以

言简意赅的巴士博弈为例

当然了这里还有一道跟博弈树有关的题

【我是那道题的链接】

SG函数

一类解决博弈论的有力玄学武器

常用于解决组合问题

具体见【SG】

基本的SG定理也就是

我们将当前游戏分解为若干子游戏之后

第i个子游戏的SG直接是SG_i(1<=i<=n)

那么总的SG值就是SG_1^SG_2......^SG_n

接下来是一道板子题【HDU 1848】

一道裸的SG函数题

我们仅需预处理出

1000以内的SG函数即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>void read(T &a)
{
    T x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=0;ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    a=f?x:-x;
}
/*-------------OI使我快乐-------------*/
int fib[N],SG[N];
bool ok[N];
int n,m,k;
int main()
{
	fib[0]=fib[1]=1;
	for(R int i=2;i<=20;++i) fib[i]=fib[i-1]+fib[i-2];
	for(R int i=1;i<=1010;++i)
	{
		memset(ok,0,sizeof ok);
		for(R int j=1;j<=20&&fib[j]<=i;++j)
		ok[SG[i-fib[j]]]=1;
		for(R int j=0;;++j) if(!ok[j]) {SG[i]=j;break;}
	}	
	read(n);read(m);read(k);
	while(n&&m&&k)
	{
		if(SG[n]^SG[m]^SG[k]) puts("Fibo");
		else puts("Nacci");
		read(n);read(m);read(k);
	}
	return 0;
}