對于hdu3032題描述如下：
Paste_Image.png
Sample Input
2
3
2 2 3
2
3 3
Sample Output
Alice
Bob
如果不可以分成兩堆莹弊，就是一個(gè)Nim的經(jīng)典游戲。對于Nim游戲，有以下結(jié)論：
a1 xor a2 xor ...xor an != 0 必勝態(tài)
a1 xor a2 xor ...xor an == 0 必?cái)B(tài)
首先泳叠，一旦從xor為零的狀態(tài)取走至少一顆石子吼过，xor就一定會(huì)變成非零城菊，所以必?cái)B(tài)只能轉(zhuǎn)移到必勝態(tài)谊路。
然后，觀察xor的二進(jìn)制表示最高位的1囱挑，選取石子數(shù)的二進(jìn)制表示對應(yīng)位也為1的某堆石子醉顽。只要從中取走使得該位變?yōu)榱悖移溆鄕or中的1也反轉(zhuǎn)的數(shù)量的石子平挑，xor就可以變?yōu)榱阌翁怼Ｒ虼耍貏賾B(tài)總是可以轉(zhuǎn)移到某個(gè)必?cái)B(tài)通熄。
所以唆涝，計(jì)算異或值就可以得到結(jié)果，非零則Alice必勝唇辨，為零則Bob必勝廊酣。
int n;//有n堆object
int arr[MAX_N];//每堆的個(gè)數(shù)
void solve() {
int x = 0;//因?yàn)?與任何數(shù)異或都為此數(shù)本身
for (int i = 0; i < n; ++i)
x ^= arr[i];
if (x != 0) puts("Alice");
else puts("Bob");
}
利用Nim的思想對sg函數(shù)打表，可以找到此題的規(guī)律赏枚。先貼上打表代碼：
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 100;
int sg[MAX_N];//sg函數(shù)
bool vis[MAX_N];//標(biāo)記數(shù)組
void solve(int n) {
memset(vis, false, sizeof(vis));
for (int i = 0; i < n; ++i)
vis[sg[i]] = true;
for (int i = 1; i <= n; ++i)//因?yàn)榭梢苑殖蓛啥淹龀郏绻眩蛯懭匮h(huán)
for (int j = 1; j <= n; ++j) {
if (i + j == n) vis[sg[i] ^ sg[j]] = true;
}
int i;
for (i = 0; ; ++i)//沒有i < n饿幅，如果都不成立凡辱，最后i = n
if (!vis[i]) break;
sg[n] = i;
cout << "sg[" << n << "]=" << i << endl;
}
int main() {
memset(sg, 0, sizeof(sg));
for (int i = 1; i < 50; ++i) {
solve(i);
}
return 0;
}
運(yùn)行結(jié)果為：
Paste_Image.png
由此可以得到題解：
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = 0;
while (n--) {
int val;
cin >> val;
if (val % 4 == 3) ans ^= val + 1;
else if (val % 4 == 0) ans ^= val - 1;
else ans ^= val;
}
cout << (ans ? "Alice" : "Bob") << endl;
}
return 0;
}
