(本篇文章将充斥着大量的大小写不分，括号中英文不分，请谅解)
本篇blog推荐的题目均是可以证明的题解（不能证明的SG函数有什么存在的必要吗（恼））
ICG
ICG就是公平组合游戏，其满足
有两个玩家轮流行动。
双方的游戏方式一致。
双方均知道游戏的完整信息。
以玩家无法行动为游戏结束。
游戏在有限步数内结束，并且一定能分出胜负。
经典的Nim游戏就是公平组合游戏的代表，但是围棋、象棋以及井字棋这些不属于，因为这三种双方的行动不同。而且像井字棋，可能存在平局。
SG函数
ICG可以看做一个图上的游戏，两人轮流在图上行走到不同的状态，并且是一个递增有界的图（就是无论你怎么走，最后一定会停下来，而不是停不下来的希望之花），然而有些状态是终止态，走到上面的人输，必胜法即一定可以让对方走到中止态的方法。
现在定义集合F(x)为点x（即状态x）所能到达的所有状态，如果F（x）为空集则x为中止状态
定义G（x）为F(x)中所有状态y的g（y）所不包含的最小非负状态（若F(x)为空则G(x)=0）
SG函数最重要的定理就是 G(X)=G({x1,x2…xn})=G(x1)^G(x2)^…^G(xn)
例题1
有n颗石子，两人轮流取，最少1颗，最多k颗，拿走最后的石子的那个人胜利
那么最后的必胜态就是0然后我们从小到大推
1可以到0
2可以到0 1
3可以到0 1 2
k可以到 k-1,k-2…0
则g(x)=x(1<=x<=k)
对于k+1其可以到1,2,3,4…k即g(k+1)=0
以此类推g(k+2)=1
我们发现这个函数是一个周期函数，周期为k+1
故任何一个数必然存在于一个周期的某一个位置，所以得到结论g(x)=x%(k+1)
对于本题如果g(n)=0则先手必胜
反之，后手一定能在f(n)找到一个y满足g(y)=0（余数性质）
变式1
我们做东方题好不好啊
ao
https://www.luogu.org/problemnew/show/U66339
其实就是把取完赢变成了取完输
也就是说只剩1颗的时候就必输了（当然只剩0颗也是必输）
也就是说先把n-1即可
但是！
这里特殊的是2——k+1颗先手还是必胜的，因为一定能把石头拿到只剩一颗
没了
例题2 POJ1067
给定两堆石子，每次可以在一堆或两堆中取任意个石子（至少1个）轮流取，取完的人嬴
网上看完了证明，感觉这题并不是很适合放在第二题，而且，这里在书信息学奥赛数学一本通里放在第二题（实际上也只有两题）不大合适，并且书上并没有给出证明
定义当前状态为一个二元组(a,b)表示两组石子分别有a,b个
显然(a,b)等价于(b,a)
首先显然的(k,0)(0,k)(k,k)都是先手必胜态
定理1：对于a!=b的二元组(a,b)先手必败态对于不同的a只有一组
若存在(a,b)(a,c)（c>b）两组
则a,c一定能被取到a,b则先手是必胜的
同样这也能解释这个游戏为什么不是必胜就是必败
定理2：若有必败(a,b) (a+k,c+k)不存在
证明和上面同理
定理3：对必败的二元组(a,b)按a排序，则b[n]=a[n]+n-1;
若前k个二元组满足b-a=第几个-1 则第k+1个二元组也满足
假设(a[n],a[n]+n-1)是必胜态则他一定可以到其他必败态
若在左边取则到了已经有的a或b且差值变大，不是必胜态
若在右边取，则差值变小，小差值的二元组已经有了且开头不是a[n]
同时差值不变，但a变小，所以不存在必败态
所以二元组的通向式就得到了，然后就可以得到网上的式子了
但实际上我感觉这题做到递推式做出来就已经有蓝题难度了（
递推式是b=[a*1.618] ([]是下取整符号)
那么接下来涉及的东西就已经不属于博弈论了XD
贝亚蒂定理
设a、b是正无理数且 1/a +1/b =1。记P={ [na] | n为任意的正整数}，Q={ [nb] | n 为任意的正整数}，([x]’指的是取x的整数部分)则P与Q是Z+的一个划分，即P∩Q为空集且P∪Q为正整数集合N+。（这玩意儿总不用我证明了吧）
这里前面我们已经证明过a,b是不相等且不重复的二元组，则他们属于贝亚蒂列
那么接下来就事解方程时间辣QAQ
已知Beatty序列：an= ⌊αn⌋，bn= ⌊βn⌋，而bn = an + n = ⌊αn⌋ + n = ⌊（α+1）n⌋，於是β = （α+1），代入1/α + 1/β = 1，解得α =（1+√5）/ 2 ≈ 1.618，這個數字就是黃金比例數！！
这段事最简单的，就粘别人blog了QAQ
没咯~~~
#include <bits/stdc++.h>
const double L = 1.6180339887;
int main()
{
long long a,b,det;
while(cin>>a>>b)
{
if(a > b) swap(a,b);
det = b-a;
if(a == int(det * L))
printf("0\n");
else printf("1\n");
}
return 0;
}
例题3 luoguP2197
你 妈 的 久 等 了
甲，乙两个人玩Nim取石子游戏
nim游戏的规则是这样的：地上有n堆石子（每堆石子数量小于10000），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这n堆石子的数量，他想知道是否存在先手必胜的策略。
比起上一题这题不知道水到哪里去了
对于一个状态{a1,a2,a3…an}
我们的结论是a1^a2^…^an=0时
先手必胜
我们设集合函数f(X)=f({x1,x2,x3,x4…xn})=x1^x2^…^xn
首先状态{0,0,0…0}必胜
对于任意一个f(x)!=0都能变成
f(y)=0
证明设f(x)最高位为a
则可以把a直接抹除或把a变成任意个更低的位数
例如现在1+2+4是异或出来的结果那么4就可以变成1+2（也就是减少1）
那么一直这么做，最后总会到达最小的那个异或为0的状态，也就是{0,0,0,0…0}（因为石子数量是递减的QAQ）
但其实这样的证明很不SG，这样子证明出来的东西不能叫SG函数，只能是一个函数
我们可以把这个问题看作把很多个并列的取石子游戏，显然，对于一堆石子x
sg(x)=x(x可以取1个到x个也就是1——x-1都可以取，根据SG函数的定义就是x了)
然后更具基本定理直接把每堆石子异或起来就好了QAQ
#include<bits/stdc++.h>
using namespace std;
int ans,n;
int t;
inline int read()
{
int tot=0;
char ch;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
return tot;
}
int main ()
{
t=read();
for(int ii=1;ii<=t;ii++)
{
n=read();
ans=0;
for(int i=1;i<=n;i++)
{
ans^=(read());
}
if(!ans) printf("No\n");
else printf("Yes\n");
}
return 0;
}
/*
1
5 1000
*/
例题4 阶梯nim游戏
好像是转换比较多的游戏，变式比较多
首先是对阶梯博弈的阐述，博弈在一列阶梯上进行，每个阶梯上放着一些石子，两个人进行阶梯博弈，每一步则是将一个集体上的至少一个石子移到前面去最后没有石子可以移动的人输
类似nim游戏的，我们将最简单的必胜局拿出来发现是只有1号位上有石子，最简单的必败局面就是只有0位上有石子
我们考虑是否存在一个能被维护的性质（即无论后手如何行动先手都可以对其进行操作使其依旧满足性质，这里不知道用什么词所以就用维护了），因为nim游戏的状态是递减的，所以最后一定能到达最小的满足该性质的必败态
我们考虑只有3个阶梯的博弈，可以发现偶数位上无论有几位都对最终答案没有影响，所以这个游戏只和奇数位上的石子数目有关，那我们直接维护奇数位上的必败态，也就是异或和为0，移动偶数就是给奇数加，移动奇数就是给奇数减，减的证明已经证明过了，加的证明同理不再赘述（就是懒）
变式1 luoguP2575
题意自己去看原题（
每一行看做一个独立的游戏，可以发现
我们的最终状态就是棋子全部扔到最右边，所以说这和阶梯nim中吧所有棋子扔到最左边很像
我们将黑色棋子看做石子，空格就是每个阶梯间的分隔，每次最多只有一个空格被移动（移动棋子只会替换掉一个空格）
然后根据SG函数的基本定理就理所当然的把每一行的SG函数值异或起来了
#include<bits/stdc++.h>
using namespace std;
int T;
int n,cnt[29],a[29],sg[29],fz[29],len,ans;
int main ()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ans=0;
for(int ii=1;ii<=n;ii++)
{
memset(cnt,0,sizeof(cnt));
scanf("%d",&len);
for(int i=1;i<=len;i++)
{
scanf("%d",&a[i]);
cnt[a[i]]++;
}
int tot=0,i=20,fg=0;
while(cnt[i]) i--;
for(;i;--i)
{
if(!cnt[i])ans^=(fg?tot:0),fg^=1,tot=0;
else ++tot;
}
ans^=(fg?tot:0);
}
if(ans) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
变式2 P3480
有N堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。
这题挺可惜的，没有自己想过，直接被其他blog剧透了QAQ
这题时真的很妙啊
我们将石子数组差分，每次去掉1颗石子相当于左边加一，右边减一（除了边界处）
也就是一个边界可以把石子扔掉的阶梯博弈
但把边界石子扔掉是没有影响的，若边界是奇数，扔掉等价于移到偶数位上
偶数位则根本没有影响
#include<bits/stdc++.h>
using namespace std;
int n,a[100100],b[100100];
int main()
{
int T,i,t;
scanf("%d",&T);
while(T--)
{
t=0;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]-a[i-1];
for(i=n;i>=1;i-=2) t^=b[i];
if(t) printf("TAK\n");
else printf("NIE\n");
}
return 0;
}
