hdu3032 Nim or not Nim? （sg打表找规律）

题目：

标准Nim游戏的基础上，增加了一个操作：可以将某堆石子分成两堆。

分析：

将石子分为两堆的操作可视为两个子游戏，那么此时的sg值就是两个子游戏sg异或值。然后打表找规律即可。

代码：

打表代码：

#include <bits/stdc++.h> using namespace std; #define ms(a,b) memset(a,b,sizeof(a)) #define lson rt*2,l,(l+r)/2 #define rson rt*2+1,(l+r)/2+1,r typedef unsigned long long ull; typedef long long ll; const int MAXN=105; const double EPS=1e-8; const int INF=0x3f3f3f3f; const int MOD = 1e9+7; int n,s[MAXN],sg[MAXN]; int getsg(int x){ if(sg[x] != -1) return sg[x]; int vis[MAXN]; ms(vis,0); for(int i=1;i<=x;i++){ vis[getsg(x-i)] = 1; } for(int i=1;i<=x-1;i++){ vis[getsg(i)^getsg(x-i)] = 1; } for(int i=0;i<MAXN;i++){ if(vis[i] == 0){ sg[x] = i; break; } } return sg[x]; } int main(){ ios::sync_with_stdio(false); n = 100; ms(sg,-1); sg[0] = 0; for(int i=1;i<=100;i++){ sg[i] = getsg(i); // cout << i << " " << sg[i] << "\n"; } for(int i=0;i<=100;i+=4){ cout << i << " " << sg[i] << endl; } return 0; }

AC代码：

#include <bits/stdc++.h> using namespace std; #define ms(a,b) memset(a,b,sizeof(a)) #define lson rt*2,l,(l+r)/2 #define rson rt*2+1,(l+r)/2+1,r typedef unsigned long long ull; typedef long long ll; const int MAXN=105; const double EPS=1e-8; const int INF=0x3f3f3f3f; const int MOD = 1e9+7; int n; int main(){ ios::sync_with_stdio(false); int T; cin >> T; while(T--){ cin >> n; int ans = 0; for(int i=1;i<=n;i++){ int x; cin >> x; if(x%4==1 || x%4==2) ans ^= x; else if(x%4==0) ans ^= (x-1); else if(x%4==3) ans ^= (x+1); } if(ans) cout << "Alice\n"; else cout << "Bob\n"; } return 0; }