将一堆石子分成多堆——Multi-SG 游戏

这类博弈只需要记住一点，一个由多个游戏组成的游戏sg值为这多个游戏的sg值异或和。

也就是所有对一整个nim游戏它的sg值即为每一小堆的sg的异或和。

hdu 5795

这题就是可以选择把一堆石子分成3堆。 通过上述方法，只需要打表找出规律即可。

#include<stdio.h>
#include<string.h>
#include <iostream>
using namespace std;

int sg[10000];
void init()//sg打表
{
    //   memset(sg,0,sizeof(sg));
    sg[0]=0;
    sg[1]=1;
    for(int i=2;i<=100;i++)
    {
        bool vis[1010]={false};
        
        
        for(int j=0;j<=i;j++)
        {
            vis[sg[j]]=true;//取石子
        }
        for(int j=1;j<i;j++)
            for(int k=1;k<i;k++)
            {
                for(int p=1;p<i;p++)
                {
                    
                    if(j+k+p==i) vis[sg[j]^sg[k]^sg[p]]=true;//拆分
                }
            }
    
        int j=0;
        while(vis[j]!=0)j++;
        sg[i]=j;
    }
}

int main()
{
    //    memset(sg,-1,sizeof(sg));
//    init();
//    for(int i=1;i<=100;i++)
//    {
//        printf("%d	",sg[i]);
//        if(i%8==0)printf("
");
//    }
//    
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        int ans = 0;
        for(int i=0;i<n;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            if(tmp%8==0)
            {
                ans ^= (tmp-1);
            }
            else if(tmp%8==7) ans ^= (tmp+1);
            else ans ^= tmp;
        }
        if(ans == 0) cout<<"Second player wins."<<endl;
        else cout<<"First player wins."<<endl;
    }
}