题目大意
Alice 与 Bob 取 n 堆石子(Alice 为先手),但每堆除数目 ai,还有一个针对 Alice 的限制 bi,具体地说:
- bi=0,则该堆对 Alice 无限制
- bi=1,则 Alice 只能在该堆取奇数个石子
- bi=2,则 Alice 只能在该堆取偶数个石子
问 Alice 是否必胜。
1≤n≤100,000
1≤ai≤1,000,000,000
题目链接
ZOJ 3964
题解
一道非公平博弈的题,则要考虑什么时候公平,以及不公平时怎么变的公平。
首先,如果有一堆石子满足 ai=1 且 bi=1,则此时这个限制是无用的,之后我们讨论的限制都是有用的限制。
如果所有堆都无有用限制,那就是普通的 NIM 游戏。
如果只有一个限制堆:
- Alice 可以将其取光,剩余石子堆为普通的 NIM 游戏。
- Alice 可以将其取至只剩一个,此时限制无用,为普通 NIM 游戏。
- 否则 Alice 对这一堆无可奈何,Bob 必胜。
如果有多个限制堆,则必有一个 Alice 无可奈何,Bob 必胜。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #include <cstdio>
const int MAXN = 100005;
int a[MAXN], b[MAXN];
void solve() { int n, nim = 0, cnt = 0; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) { scanf("%d", &b[i]); if (b[i] == 1 && a[i] == 1) b[i] = 0; if (!b[i]) nim ^= a[i]; else ++cnt; } if (cnt > 1) { puts("Bob"); return; } else if (cnt == 0) { puts(nim ? "Alice" : "Bob"); return; } bool ans = true; for (int i = 0; i < n; i++) if (b[i]) { if (b[i] % 2 == a[i] % 2) { ans = !nim; } else if (b[i] == 1) { ans = nim == 1; } else { ans = false; } } puts(ans ? "Alice" : "Bob"); }
int main() { int T; scanf("%d", &T); while (T--) solve(); return 0; }
|