基础知识：

　　        

　　

1.

算法思路：bash博弈模板

#include
      
       using namespace std;int main(){    int t,n,m;cin>>t;    while(t--)    {        scanf("%d%d",&n,&m);        if(n%(m+1)==0) cout<<"second"<
      

算法思路：bash博弈模板加输出先手必赢的第一项，注意n<=m的时候

#include
      
       using namespace std;int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        if(n%(m+1)==0) cout<<"none"<
      

算法思路： bash博弈模板

#include
      
       using namespace std;int main(){    int t,n,m;cin>>t;    while(t--)    {        scanf("%d%d",&n,&m);        if(n%(m+1)==0) cout<<"Rabbit"<
      

算法思路：bash博弈模板

#include
      
       using namespace std;int main(){    int n,m;    while(~scanf("%d%d",&n,&m),n+m)    {        if((n-1)%(m+1)==0) cout<<"Jiang"<
      

算法思路：n,p必胜必败点分析，终结状态设为p；存在后继p，则为n；任意后继均为n，则为p；

#include
      
       using namespace std;int main(){    int n,m;    while(~scanf("%d%d",&n,&m),n+m)    {        if(n&1&&m&1) printf("What a pity!\n");        else printf("Wonderful!\n");    }    return 0;}
      

算法思路：斐波那契博弈模板

#include
      
         using namespace std;  int f[100];  int main()  {      f[1]=1,f[2]=1;      for(int i=3;i<=48;i++)          f[i]=f[i-1]+f[i-2];      int n;      while(~scanf("%d",&n),n)      {          int flag=1;          for(int i=2;i<=48;i++)              if(f[i]==n) flag=0;          if(flag) printf("First win\n");          else printf("Second win\n");      }                  return 0;  }
      

算法思路：威佐夫博弈模板

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int main(){    int n,m;double tmp=(sqrt(5)+1)/2;    while(~scanf("%d%d",&n,&m))    {        if(n>m) swap(n,m);        int b=(m-n)*tmp;        if(n==b) printf("0\n");        else printf("1\n");     }    return 0;}
          
         
        
       
      

算法思路：威佐夫博弈模板，并输出第一次取的情况，注意性质.任何自然数都包含在一个且仅有一个的奇异局势中，一个自然数差值对应一个奇异局势

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int main(){    int n,m;double tmp=(sqrt(5)+1)/2;    while(scanf("%d%d",&n,&m),n+m)    {        if(n>m) swap(n,m);        int b=(m-n)*tmp;        if(n==b) printf("0\n");        else         {            printf("1\n");            if(b<=n) //从两堆中拿走相同数量的                printf("%d %d\n",b,b+m-n);            //从一堆中取             if(n==0||m==0) printf("0 0\n");            for(int i=1;i<=m;i++)            {                b=i*tmp;                if(b==tmp) continue;                if(b==n&&b+i<=m) printf("%d %d\n",b,b+i);                else if(b+i==n&&b<=m) printf("%d %d\n",b,b+i);                else if(b<=n&&b+i==m) printf("%d %d\n",b,b+i);                else if(b+i<=n&&b==m) printf("%d %d\n",b,b+i);            }        }    }    return 0;}
          
         
        
       
      

算法思路：nim博弈模板，注意(a[i]^xor_sum<a[i]）这东西会出错的，应令tmp=a[i]^xor_sum；异或运算很巧妙啊

#include
      
       using namespace std;int a[101],n;int main(){    while(~scanf("%d",&n),n)    {        int xor_sum=0,num=0;        for(int i=1;i<=n;i++)        {            scanf("%d",&a[i]);            xor_sum^=a[i];        }        for(int i=1;i<=n;i++)        {            int tmp=a[i]^xor_sum;            if(tmp
      

 

算法思路：可以用必胜态，必败态分析，同理也可用sg函数打表，sg[x]=0即对应必败态，sg[x]!=0即代表必胜态，两者等同的关系

#include
      
       using namespace std;const int maxn=1010;int f[maxn],sg[maxn],vis[maxn];void getsg(){    memset(sg,0,sizeof(sg));    for(int i=1;i<=maxn;i++)    {        memset(vis,0,sizeof(vis));        for(int j=1;f[j]<=i;j++)            vis[sg[i-f[j]]]=1;        for(int j=0;j
      

算法思路：nim牌 sg函数 取各个游戏的异或和

#include
      
       using namespace std;const int maxn=1010;int f[maxn],sg[maxn],vis[maxn];int getsg(int n){    memset(sg,0,sizeof(sg));    for(int i=1;i<=maxn;i++)    {        memset(vis,0,sizeof(vis));        for(int j=1;f[j]<=i;j++)            vis[sg[i-f[j]]]=1;        for(int j=0;j