HDU5795 A Simple Nim sg函數

題目連結：HDU5795

A Simple Nim

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 618    Accepted Submission(s): 394

Problem Description Two players take turns picking candies from n heaps,the player who picks the last one will win the game.On each turn they can pick any number of candies which come from the same heap(picking no candy is not allowed).To make the game more interesting,players can separate one heap into three smaller heaps(no empty heaps)instead of the picking operation.Please find out which player will win the game if each of them never make mistakes.  

Input Intput contains multiple test cases. The first line is an integer  1≤T≤100 , the number of test cases. Each case begins with an integer n, indicating the number of the heaps, the next line contains N integers  s[0],s[1],....,s[n−1] , representing heaps with  s[0],s[1],...,s[n−1]  objects respectively. (1≤n≤106,1≤s[i]≤109)  

Output For each test case,output a line whick contains either"First player wins."or"Second player wins".  

Sample Input

2
2
4 4
3
1 2 4
        

Sample Output

Second player wins.
First player wins.
        

  題意：Nim遊戲，有很多堆糖果，每個人可以在一堆取走任意多個糖果，或者将其分成3個非空堆。最後取走為勝，問先手勝還是後手。 題目分析：求SG函數，首先對于一個大小為x的堆，可以分成任意數量的3堆以及從0到x-1的任意數，将這些情況下的sg值分别異或和就是x的sg值，這裡分成3堆的sg值為分成3堆的個數的異或和。對于所有數x的sg值可以打表找規律，求出每個數的sg值後對于任意堆數的sg值為每一堆的sg值異或和，為0就是必輸局。

打表程式：

//
//  main.cpp
//  A Simple Nim list
//
//  Created by teddywang on 2016/8/9.
//  Copyright © 2016年 teddywang. All rights reserved.
//
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<ctime>
using namespace std;
int sg[1010];
int vis[1010];

int getsg(int x)
{
    if(sg[x]!=-1) return sg[x];
    memset(vis,0,sizeof(vis));
    for(int i=1;i<x;i++)
    {
        int a=getsg(i);
        for(int j=1;j<x-i;j++)
        {
            int buf=a;
            int b=getsg(j);
            int c=getsg(x-i-j);
            buf^=b;buf^=c;
            vis[buf]=1;
        }
        vis[a]=1;
    }
    vis[0]=1;
    for(int i=1;;i++)
    {
        if(!vis[i]) return i;
    }
}

int main()
{
    memset(sg,-1,sizeof(sg));
    sg[0]=0,sg[1]=1,sg[2]=2;
    for(int i=0;i<1000;i++)
    {
        sg[i]=getsg(i);
        printf("sg[%d]=%d\n",i,sg[i]);
    }
}
           

程式代碼：

//
//  main.cpp
//  A Simple Nim
//
//  Created by teddywang on 2016/8/4.
//  Copyright © 2016年 teddywang. All rights reserved.
//

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;


int getsg(int x)
{
    if(x<=2) return x;
    else if(x%8==0) return x-1;
    else if(x%8==7) return x+1;
    else return x;
}

int main()
{
    int T,n;
    cin>>T;
    while(T--)
    {
        scanf("%d",&n);
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            int buf;
            scanf("%d",&buf);
            cnt^=getsg(buf);
        }
        if(cnt!=0) printf("First player wins.\n");
        else printf("Second player wins.\n");
    }
}