博弈论专题（持续更新）

类型一：Nim和问题

这类问题的识别特点是（非严谨）：两个人轮流从任意多堆物品中选一堆，拿走至少一个（可以全拿走）

解决办法是：对所有的堆的大小求异或，如果结果不为0，那么先手胜，结果为0，先手败

模板题目：https://www.luogu.com.cn/problem/P2197#submit

 AC代码：

#include<iostream>
using namespace std;
int main()
{ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
  int t;
  cin>>t;
  while(t--)
  {
    int n;
    cin>>n;
    long long int sum=0;
    for(int i=1;i<=n;i++)
    {int p;
      cin>>p;
      sum^=p;//核心，对所有的堆的大小进行异或
    }
    if(sum==0) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
  }
  return 0;

}

类型二：SG问题

这类问题可以看做是Nim问题的进阶，Nim问题要求每个人可以拿1个到n个，没有限制，而SG问题面对的是限制了可拿个数的问题，比如每人只能拿1个或者3个，每人只能拿偶数个等等

解决方案：利用SG公式（参考博客：https://blog.csdn.net/qq_35914587/article/details/79502641?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param）

我太弱了，也说不清楚，就看大犇博客吧

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1848

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[40],SG[1010],S[1010];
void  get_SG()//与Nim和问题不同之处
{
  memset(SG,0,sizeof(SG));//SG【0】=0
  for(int i=1;i<=1000;i++)//依次计算SG的值
  {memset(S,0,sizeof(S));//每次都要清除后继，后继就是当前有几个石子被拿走几个后，还剩下的，可以理解为被拿走之后可能的取值
    for(int j=0;j<29&&f[j]<=i;j++)//根据题目大小，f数组记录可以拿走多少个，依次遍历，看看每次拿走相应个数后剩下的值
    {//i-f【j】就是拿走f【j】个之后，石子堆还剩下几个
      S[SG[i-f[j]]]=1;//S中记录的是抽完可能值的SG，不是抽完可能值它本身
    }
    for(int j=0;;j++)
    {
      if(S[j]==0)
      {
        SG[i]=j;
        break;
      }
    }
  }
}
int main()
{ ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  f[0]=f[1]=1;
  for(int i=2;i<=29;i++)
  {
   f[i]=f[i-1]+f[i-2];
  }//统计每次能拿的值
   get_SG();//获取SG值
  int m,n,p;
  while(cin>>m>>n>>p&&(m||n||p))
  {
    if(SG[m]^SG[n]^SG[p]) cout<<"Fibo"<<endl;//和Nim函数类似
    else cout<<"Nacci"<<endl;
  }

  return 0;
}