bash game

情况介绍

两个顶尖聪明的人在玩游戏，有n个石子，每人可以随便拿1−m个石子，不能拿的人为败者，问谁会胜利

分析

可以想到如果最终剩下m+1个石子，那么肯定先手必败。那么我们想到推出其他的m+1的倍数也就是说如果
n%(m+1)!=0也就是说n=k(m+1)+r (k,r为常数)那么我们先手可以完全先拿走r个石子然后后手不管你怎么拿我先手只要凑够m+1就行了最终肯定是先手能够获胜反之如果n=k(m+1)那么后手必胜所以我们可以得到最终代码

if(n%(m+1))
cout<<"first\n";
else
cout<<"second\n";

威佐夫博弈

情况介绍

有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。

分析

具体的推理我就不说了，网上各种推理。也就是说我们要判断当前状态(a,b)是否可以先手胜利的条件是求a,b的最大值然后求出差值来b-a然后看看(b-a)* r是不是等于a其中r是(1+sqrt(5))/2

int n,m;
cin>>n>>m;
int t1=min(n,m);
int t2=max(n,m);
int t3=t2-t1;
double r=(1+sqrt(5))/2;
int t4=r*t3;
if(t4==t1)
cout<<"Yes";
else
cout<<"no";

Nim game

情况介绍

有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

分析

这个就是一个比较常见的会出现变形的
首先接受NP
N为必胜点P为必败点
也就是说当前如果是N点那么经过两者的正确的操作那么先手必胜P点也是这样
其中包含三个性质
①N至少存在一种进入P
②P只能进入N
③所有的终结一定是P
也就是说如果当前是P那么下一点必须是N
如果要判断当前情况是不是N那么我们可以把当前的所有的数异或一下然后看看是不是等于0如果等于0那么就是一个P否则是一个N
这也就是nim和

int sum=0;
for(int i=0;i<n;i++)
{
  cin>>num[i];
  sum^=num[i];
}
if(sum)
cout<<"Yes";
else
cout<<"no";

SG函数

一看到这个我就想到csgo的SG553我自称他为帅哥函数或者傻狗函数。。。

分析

SG函数可以直接求出当前节点的NP属性如果SG[n]大于0那么代表当前的n是一个N否则是P

求解

SG函数靠递推求解，保证每次S集合都要清空即可

for(int i=1;i<=n;i++)
{
  memset(s,0,sizeof(s));
  for(int j=1;i-f[j]>=0&&j<=N;j++) //求解当前延伸
  s[sg[i-f[j]]]=1;
  for(int j=0;;j++) //求解最小的没有出现的整数
  if(!s[j])
  {
    sg[i]=j
    break;
  }
}