题解 | #甜蜜的博弈#

题解：BISHI34 甜蜜的博弈

题目链接

题目描述

有一堆钻石，进行如下回合制游戏：Alice 先手、Bob 后手，双方轮流操作。设当前剩余钻石数量为 $N$ 。每回合玩家可按题面给出的三种合法方式之一移除若干颗钻石（其中包含“移除 $1$ 颗”和“移除 $2$ 颗”的选项）。当某位玩家无法进行操作时，该玩家失败。给定 $T$ 组询问，每组给定初始 $N$ ，若双方最优博弈，判断胜者（输出 Alice 或 Bob）。

样例：当 $N=1$ 输出 Alice；当 $N=3$ 输出 Bob；当 $N=5201314$ 输出 Alice。

解题思路

这是一个依赖状态的减法博弈。设 $f(N)$ 表示先手在剩余 $N$ 颗时是否必胜。可行动作：

任意 $N\ge 1$ ，可取 $1$ ；
若 $N$ 为偶数且 $N\ge 2$ ，可取 $2$ ；
若 $5\mid N$ 且 $N\ge 5$ ，可取 $5$ 。

先列出小值：

$N=1,2,4,5,7,8,10$ 为必胜； $N=3,6,9$ 为必败。

归纳分类：

对所有偶数 $N\ge 8$ ， $N-1$ 为奇数且 $\ge 7$ 。当 $N\ge 10$ 时， $N-1\ge 9$ 为必败，故 $N$ 必胜； $N=8$ 可取 $2$ 到 $6$ （必败），亦必胜。结合 $N=2,4$ ，仅 $N=6$ 为偶数必败。
对所有奇数 $N\ge 9$ ，所有可达状态为偶数（ $N-1$ ，以及若 $5\mid N$ 则 $N-5$ ），且它们 $\ge 4$ ，均为必胜，故该类奇数为必败。

结论（与样例一致）：

若 $N\in\{3,6\}$ 或 $N\ge 9$ 且为奇数，则 Bob 胜；
否则 Alice 胜。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        long long N; 
        cin >> N;
        bool bob = (N == 3 || N == 6 || (N >= 9 && (N % 2 == 1)));
        cout << (bob ? "Bob" : "Alice") << '\n';
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long N = sc.nextLong();
            boolean bob = (N == 3 || N == 6 || (N >= 9 && (N % 2 == 1)));
            System.out.println(bob ? "Bob" : "Alice");
        }
    }
}

T = int(input())
for _ in range(T):
    N = int(input())
    bob = (N == 3 or N == 6 or (N >= 9 and (N % 2 == 1)))
    print("Bob" if bob else "Alice")

算法及复杂度

算法：减法博弈分类归纳；偶数除 $6$ 外必胜，奇数且 $\ge 9$ 必败
时间复杂度： $\mathcal{O}(T)$
空间复杂度： $\mathcal{O}(1)$