HDOJ 3032 Nim or not Nim?

题目链接：HDOJ3032

跟HDOJ 5795没有本质区别吧，一个是两堆，一个是三堆，本质是一样的

HDOJ5795题解

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+100;
int t,n;
int sg[maxn];
int ans,num;

int g(int x){
	int mex[maxn/100];
	if (sg[x]!=-1) return sg[x];
	memset(mex,0,sizeof(mex));
	for(int i=0;i<x;i++)
		mex[sg[i]]=1;
	for(int i=1;i<=x/2;i++){
		int a=sg[i];
		int b=sg[x-i];
		mex[a^b]=1;
	}
	for(int i=0;;i++)
		if (!mex[i]) return sg[x]=i;
}

int main(){
	//freopen("input.txt","r",stdin);
	//memset(sg,-1,sizeof(sg));
	//for(int i=0;i<=100;i++)
	//	printf("sg[%d]:%d\n",i,g(i));
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		ans=0;
		while(n--){
			scanf("%d",&num);
			//ans=ans^g(num);
			//printf("%d\n",g(num));
			if (num%4==3) ans=ans^(num+1);
			else if (num%4==0) ans=ans^(num-1);
			else ans=ans^num;
		}
		if (ans) puts("Alice");
		else puts("Bob");
	}
	return 0;
}