Nim or not Nim? HDU - 3032

题意: 2人博弈 , m堆个数为n[i]的石堆,  每一轮, 有两种操作

1.一堆石子取任意个

2.把一堆石头拆分成2堆非空堆

思路:先是手写了一下博弈树. 发现 g[0]=0 ,  g[1]=1, g[2]=2, g[3]=4,g[4]=3,g[5]=5  再打个SG表,get_sg的复杂度是 n,1e6  因此这题我们只能打SG表看n和sg[n]的规律

// SG函数打表
//SG函数版本
#include<cstdio>
#include<vector>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e3+3;
const int MOD=1e9+7;
const double EPS=1e-10;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
int sg[N];
bool vis[N];
int f[N];
void get_sg(){
    memset(sg,0,sizeof sg);
    sg[0]=0;
    for(int n=1;n<=1000;n++){
        memset(vis,0,sizeof vis);
        for(int j=1;j<=n;j++){
            vis[sg[j]]=1;
            if(j!=1 &&j!=n) vis[sg[j]^sg[n-j]]=1;
        }
        for(int i=0;i<=1000;i++){
            if(!vis[i]){
                sg[n]=i;
                break;
            }
        }
    }
    return ;
}
int main(void){
    get_sg();
    for(int i=1;i<=100;i++){
        cout << sg[i] <<" ";
        if(i%4==0)  cout << endl;
    }

    return 0;
}

#include<cstdio>
#include<vector>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=10005;
const int MOD=1e9+7;
const double EPS=1e-10;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}

int main(void){
    int T;
    sf(T);
    while(T--){
        int n;sf(n);
        int res=0;
        for(int i=1;i<=n;i++){
            int te;sf(te);
            if(te%4==0) te--;
            else if(te%4==3)    te++;
            res^=te;
        }
        if(res==0)  printf("Bob\n");
        else    printf("Alice\n");
    }

    return 0;
}