HDU-3032Nim or not Nim?(SG打表)

发布于 2020-10-30  0 次阅读


题目大意:

Nim or not Nim?
Alice和Bob做游戏,共有n堆石子,没堆石子为s [ i ] s[i]s[i]个,每一次可以从任意一堆中拿走任意个石子,也可以将一堆石子分为两个小堆。先拿完者获胜。
Alice先手

思路:

用SG打表后

在这里插入图片描述

发现规律是
x = x − 1   w h e n   ( x % 4 = = 0 )
x = x + 1   w h e n   ( x % 4 = = 3 )
在用SG打表时,注意操作将一堆分成两堆即为枚举分成两堆的情况
最后用得到的规律算出每堆的值求异或即可

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=105;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int vis[N], sg[N];
void init(int n) {
    sg[0]=0;sg[1]=1;
	for (int i = 2; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		for (int j = 0; j <= i; j++) vis[sg[i - j]] = true;
		for (int j = 0; j <= i; j++) vis[sg[j] ^ sg[i - j]] = true;
		int j=0;
        while(vis[j]!=0) j++;
        sg[i]=j;
	}
	for (int i = 1; i < n; i++){
        cout<<sg[i]<<" ";
        if(i%4==0) cout<<endl;
    }
}
int n, x;
void solve(){
    cin>>n;
    int ans=0;
    for(int i=1; i<=n; ++i){
        cin>>x;
        if(x%4==0) --x;
        else if(x%4==3) ++x;
        ans^=x;
    }
    if(ans==0)  cout<<"Bob"<<endl;
    else        cout<<"Alice"<<endl;
}

signed main(){
    // init(N);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}

平平无奇的在校大学生