HDU 3032 Nim or not Nim? （需求的游戏SG功能）

意甲冠军：经典Nim游戏转换，给你n礧pi，每个堆栈有pi石头，

Alice和Bob轮流石头，意一堆中拿走随意个石子，也能够将某一堆石子分成两个小堆

（每堆石子个数必须不能为0）。先拿完者获胜

思路：求SG函数后找规律。

#include<cstdio>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<map>

#include<cmath>

#include<iostream>

#include <queue>

#include <stack>

#include<algorithm>

#include<set>

using namespace std;

#define INF 1e8

#define eps 1e-8

#define LL long long

#define maxn 1000001

#define PI acos(-1.0)

int sg[maxn],vis[maxn];

void SG()

{

	sg[0]=0;

	sg[1]=1;

	for(int i=2;i<100;i++)

	{

		memset(vis,0,sizeof(vis));

		for(int j=i-1;j>=0;j--)

		{

			vis[sg[j]]=1;

		}

		for(int j=1;j<i;j++)

		{

			int state=sg[j]^sg[i-j];

			vis[state]=1;

		}

		for(int j=0;j<maxn;j++)

		{

			if(!vis[j])

			{

				sg[i]=j;

				break;

			}

		}

	}

	for(int i=97;i<maxn;i+=4)

	{

		sg[i]=i;

		sg[i+1]=i+1;

		sg[i+2]=i+3;

		sg[i+3]=i+2;

	}

}

int main()

{

	SG();

	int t;

	scanf("%d",&t);

	while(t--)

	{

		int n;

		scanf("%d",&n);

		int st=0;

		for(int i=0;i<n;i++)

		{

			int a;

			scanf("%d",&a);

			int p=a%4;

			int m;

			if(p==0)

			{

				m=a-1;

			}

			else if(p==3)

				m=a+1;

			else m=a;

			st^=m;

		}

		if(st==0)

			printf("Bob\n");

		else printf("Alice\n");

	}

	return 0;

}