A Simple Nim
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 79 Accepted Submission(s): 48
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
2
4 4
3
1 2 4
Sample Output
Second player wins.
First player wins.
First player wins.
Author
UESTC
Source
Recommend
wange2014
题意：给定n堆石子，每次有两种操作，1是从任意一堆中取任意个，2是把一堆分为三堆且这三堆都不为空，问谁能赢。
题解：首先看题目的数据范围是1e9，那么算出每个sg肯定会超时，所以我们想到打表找规律。首先我们暴力打表算出200以内的sg函数值，对于一堆石子来说处理出他的所有后继情况。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int sg[]= {};
bool vis[];
int t,cas=;
void get()
{
memset(sg,,sizeof(sg));
sg[]=;
for(int i=; i<=; i++)
{
memset(vis,,sizeof(vis));
for(int j=;j<=i;j++)
{
for(int k=;j+k<=i;k++)
{
if(j!=&&k!=&&((i-j-k)!=))
vis[sg[j]^sg[k]^sg[i-j-k]]=;//操作
}
}
for(int j=;j<i;j++)//操作
vis[sg[j]]=;
for(int x=; ; x++)
if(!vis[x])
{
sg[i]=x;
break;
}
}
}
int main()
{
get();
for(int i=;i<=;i++)
printf("i: %d %d\n",i,sg[i]);
return ;
}
运行该代码，我们会得到如下结果：
注意在这个表当中
观察结果我们可以得知，当n为8的倍数时，sg(n)=n+1; 当(n+1)为8的倍数时，sg(n)=n-1; 否则sg(n)=n;
所以我们把sg值异或起来就能判断出谁赢了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
long long x,ans=;
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%lld",&x);
if(x%==)
ans=ans^(x-);
else if((x+)%==)
ans=ans^(x+);
else
ans=ans^x;
}
if(ans)
puts("First player wins.");
else
puts("Second player wins.");
}
return ;
}