「Codeforces 1738C」Even Number Addicts - 博弈论

发表于 分类于 ， 阅读次数： Disqus：

题意描述

Codeforces 链接

Alice 和 Bob 玩一个游戏，这个游戏中有一个有 \(n\) 项的序列 \(a\)，Alice 先手，两人轮流在 \(a\) 中取走一个数。若最终取完后 Alice 取走的数的和为偶数则 Alice 获胜，否则 Bob 获胜。若两人均按最优策略决策，求出最终的获胜方。

解题思路

目前问题过于复杂，我们可以先考虑一个简单问题：若序列 \(n\) 中只有奇数，谁会赢？

这个问题答案显然。若 \(n \bmod 4 = 1\) 或 \(n \bmod 4 = 2\) 时 Bob 赢，否则 Alice 赢。

接下来我们把偶数加进来，我们设奇数个数为 \(\text{cnt1}\)，偶数个数为 \(\text{cnt0}\)。对于 \(\text{cnt0} \bmod 2 = 0\) 的情况与 \(n\) 全为奇数的情况相同。因为只要其中有一个人选了偶数，则下一个人立即选偶数，相当于转化为 \(\text{cnt0} - 2\) 的局面，这样周而复始可将 \(\text{cnt0}\) 消为 \(0\)。且后手跟着先手选偶数的抉择对于 Alice 和 Bob 均是最优策略。

接下来我们考虑 \(\text{cnt0} \bmod 2 = 1\) 的情况。我们依然可以将 \(\text{cnt1} \bmod 4\) 的情况分类讨论：当 \(\text{cnt1} \bmod 4 = 1\) 时，Alice 最优策略是取走“唯一的”偶数，然后 Alice 必胜；当 \(\text{cnt1} \bmod 4 = 0\) 或 \(\text{cnt1} \bmod 4 = 3\) 时，Alice 最优策略是无论如何都不取“唯一的”偶数，然后 Alice 必胜；当 \(\text{cnt1} \bmod 4 = 2\) 时，无论 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
#include <cstdio>
#include <iostream>

void solve() {
    int n;
    int cnt0 = 0, cnt1 = 0;

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int a;
        scanf("%d", &a);
        if (a % 2)
            cnt1++;
        else
            cnt0++;
        cnt0 &= 1;
    }

    if (cnt0 == 0) {
        if ((cnt1 % 4 == 1 || cnt1 % 4 == 2))
            puts("Bob");
        else
            puts("Alice");
    } else {
        if ((cnt1 % 4 == 1 || cnt1 % 4 == 3 || cnt1 % 4 == 0))
            puts("Alice");
        else
            puts("Bob");
    }
}

int main() {
    int t;

    scanf("%d", &t);

    while (t--) solve();

    return 0;
}