题解 | #甜蜜的博弈#

题目链接

甜蜜的博弈

题目描述

Alice 和 Bob 玩一个取钻石的游戏。初始有 $N$ 颗钻石，两人轮流取。当轮到某个玩家时，如果剩余 $k$ 颗钻石，该玩家可以执行以下操作之一：

如果 $k \ge 1$ ，可以移除 $1$ 颗钻石。
如果 $k \ge 2$ 且 $k$ 是 $2$ 的倍数，可以移除 $2$ 颗钻石。
如果 $k \ge 5$ 且 $k$ 是 $5$ 的倍数，可以移除 $5$ 颗钻石。

当轮到某位玩家时，如果他无法进行任何操作，则该玩家输。Alice 先手，假设双方都采取最优策略，判断谁将获胜。

解题思路

这是一个典型的公平组合游戏，其核心是判断每个状态是必胜态还是必败态。

必败态 (P-position)：在该状态下，无论玩家如何操作，都会转移到对手的必胜态。
必胜态 (N-position)：在该状态下，玩家至少有一种操作能将游戏转移到对手的必败态。

$N=0$ 是一个必败态。我们可以从小到大递推计算每个状态的胜负情况。一个状态是必胜态，当且仅当它能转移到一个必败态。通过推导，我们可以得到小数值 $N$ 的胜负情况：

$N < 12$ 的必败态（Bob获胜）为： $3, 6, 9, 11$ 。
其他 $N < 12$ 的情况均为必胜态（Alice获胜）。

当 $N$ 增大时，我们会发现一个稳定的规律。对于所有 $N \ge 12$ ：

如果 $N$ 是偶数，则该状态为 必胜态。
如果 $N$ 是奇数，则该状态为 必败态。

这个规律可以通过数学归纳法证明。简单来说，对于一个大于等于 $12$ 的偶数 $N$ ，总可以通过拿走 $1$ 颗钻石，将局面变为 $N-1$ （一个大于等于 $11$ 的奇数）。而任何大于等于 $11$ 的奇数都是必败态，因此偶数 $N$ 是必胜态。相反，对于一个大于等于 $13$ 的奇数 $N$ ，所有合法的操作（拿走 $1$ 或 $5$ 颗）都会使剩余钻石数变为偶数，从而将一个必胜态留给对手，因此奇数 $N$ 是必败态。

综上，我们的解题策略是：

如果 $N < 12$ ，则判断 $N$ 是否为 $3, 6, 9, 11$ 中的一个。如果是，Bob胜；否则Alice胜。
如果 $N \ge 12$ ，则判断 $N$ 的奇偶性。如果是奇数，Bob胜；否则Alice胜。

代码

cpp
java
python

#include <iostream>
#include <set>

using namespace std;

int main() {
    int t;
    cin >> t;
    set<int> lose_small = {3, 6, 9, 11};
    while (t--) {
        int n;
        cin >> n;
        if (n < 12) {
            if (lose_small.count(n)) {
                cout << "Bob" << endl;
            } else {
                cout << "Alice" << endl;
            }
        } else {
            if (n % 2 != 0) {
                cout << "Bob" << endl;
            } else {
                cout << "Alice" << endl;
            }
        }
    }
    return 0;
}

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<Integer> lose_small = new HashSet<>();
        lose_small.add(3);
        lose_small.add(6);
        lose_small.add(9);
        lose_small.add(11);
        
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            if (n < 12) {
                if (lose_small.contains(n)) {
                    System.out.println("Bob");
                } else {
                    System.out.println("Alice");
                }
            } else {
                if (n % 2 != 0) {
                    System.out.println("Bob");
                } else {
                    System.out.println("Alice");
                }
            }
        }
    }
}

lose_small = {3, 6, 9, 11}

t = int(input())
for _ in range(t):
    n = int(input())
    if n < 12:
        if n in lose_small:
            print("Bob")
        else:
            print("Alice")
    else:
        if n % 2 != 0:
            print("Bob")
        else:
            print("Alice")

算法及复杂度

算法：博弈论、数学归纳、打表找规律
时间复杂度：对于每个测试用例，我们只进行了几次判断和取模操作，复杂度是 $\mathcal{O}(1)$ 。总的时间复杂度为 $\mathcal{O}(T)$ ，其中 $T$ 是测试用例的数量。
空间复杂度：只需要常数空间存储少量预处理信息，复杂度为 $\mathcal{O}(1)$ 。