對于hdu3032題描述如下：

Paste_Image.png

Sample Input

2
3
2 2 3
2
3 3

Sample Output

Alice
Bob

如果不可以分成兩堆，就是一個Nim的經典游戲。對于Nim游戲，有以下結論：

a1 xor a2 xor ...xor an != 0 必勝態(tài)
a1 xor a2 xor ...xor an == 0 必敗態(tài)

首先，一旦從xor為零的狀態(tài)取走至少一顆石子，xor就一定會變成非零，所以必敗態(tài)只能轉移到必勝態(tài)。
然后，觀察xor的二進制表示最高位的1，選取石子數的二進制表示對應位也為1的某堆石子。只要從中取走使得該位變?yōu)榱悖移溆鄕or中的1也反轉的數量的石子，xor就可以變?yōu)榱恪Ｒ虼?，必勝態(tài)總是可以轉移到某個必敗態(tài)。
所以，計算異或值就可以得到結果，非零則Alice必勝，為零則Bob必勝。

int n;//有n堆object
int arr[MAX_N];//每堆的個數

void solve() {
    int x = 0;//因為0與任何數異或都為此數本身
    for (int i = 0; i < n; ++i)
        x ^= arr[i];
    if (x != 0) puts("Alice");
    else puts("Bob");
}

利用Nim的思想對sg函數打表，可以找到此題的規(guī)律。先貼上打表代碼：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 100;
int sg[MAX_N];//sg函數
bool vis[MAX_N];//標記數組

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)//因為可以分成兩堆，如果三堆，就寫三重循環(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;
}

運行結果為：

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;
}