[ZOJ 3964] Yet Another Game of Stones

发表于

题目大意

Alice 与 Bob 取 $n$ 堆石子（Alice 为先手），但每堆除数目 $a_i$，还有一个针对 Alice 的限制 $b_i$，具体地说：

  • $b_i = 0$，则该堆对 Alice 无限制
  • $b_i = 1$，则 Alice 只能在该堆取奇数个石子
  • $b_i = 2$，则 Alice 只能在该堆取偶数个石子

问 Alice 是否必胜。

$1 \leq n \leq 100,000$

$1 \leq a_i \leq 1,000,000,000$

题目链接

ZOJ 3964

题解

一道非公平博弈的题，则要考虑什么时候公平，以及不公平时怎么变的公平。

首先，如果有一堆石子满足 $a_i = 1$ 且 $b_i = 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;
}