博客

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5795

解法：

先打表找规律！！！！！根据nim游戏的规则，我们可以先打印出该子游戏1~100的SG函数值，发现它的sg函数值在x%8==7的时候加了1.在x%8==0是减了1.其他的均不变。

打表程序：

#include <algorithm>
#include <string>
#include <iostream>
#include <string.h>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define LL __int64
#define maxn 100008
int SG[1000];
int sg(int x)
{
    if(SG[x]!=-1) return SG[x];
    if(x<3)
    {
        return SG[x]=x;
    }
        int vis[1000]={0,0};
        for(int i=0;i<x;i++)
        {
            vis[sg(i)]=1;
        }
        for(int i=1;i<x;i++)
        {
            for(int j=i;j+i<x;j++)
            {
                vis[sg(i)^sg(j)^sg(x-i-j)]=1;
            }
        }
        for(int i=0;;i++)
        {
            if(!vis[i]) return SG[x]=i;
        }
}
int main()
{
  freopen("in.txt","w",stdout);
  memset(SG,-1,sizeof SG);
  for(int i=0;i<=100;i++)
  {
      printf("%d  %d\n",i,sg(i));
  }

}

#include <algorithm>
#include <string>
#include <iostream>
#include <string.h>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define LL __int64
#define maxn 100008
int SG[1000];
int sg(int x)
{
    if(x<3) return x;
    if(x%8==7) return x+1;
    else if(x%8==0) return x-1;
    return x;

}
int main()
{
    int n,t;
    scanf("%d",&t);
    while(t--)
    {
        int ans=0,x;
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d",&x);
            ans^=sg(x);
        }
        if(ans) puts("First player wins.");
        else puts("Second player wins.");
    }

}