LightOJ-1199 Partitioning Game
题意： 给定n堆石头，alice和bob可以将石头分为不相等的两堆， 直到分到不能再分是时候。Alice先手。
分析： 先用sg定理打个表。
对于一堆有x个石子的堆， 他的后继状态有
{{1, x - 1};{2, x - 2};{3, x - 3};........{(x - 1)/2, x - (x - 1)/2} //保证两个堆不相等
}
对于分出来的两堆他们相互独立， 运用SG定理 求得 mex {sg(1) ^ sg ( x - 1), sg(2) ^ sg(x - 2) … sg((x - 1) / 2) ^ sg((x - (x - 1) / 2))} 打出sg表
#include <bits/stdc++.h>using namespace std;const int MAXN = 1e4 + 10;
int sg[MAXN], s[MAXN];void getSG() {int i, j;memset(sg, 0, sizeof(sg));for (i = 1; i < MAXN; i++) {memset(s, 0, sizeof(s));for (j = 1; j*2 < i && j < MAXN; j++) {s[sg[j] ^ sg[i - j]] = 1;}for (j = 0; ; j++) if (!s[j]) {sg[i] = j;break;}}
}
int main () {getSG();//for (int i = 0; i < 100; i++) cout << i << " " << sg[i] << endl;int t, n, kase = 0, x;cin >> t;while (t--) {cin >> n;int status = 0;for (int i = 0; i < n; i++) {cin >> x;status ^= sg[x];}cout << "Case " << ++kase << ": " << (status == 0 ? "Bob" : "Alice") << "\n";}return 0;
}