题解 | #【模板】巴什博弈#

题目链接

【模板】巴什博弈

题目描述

有一堆石子，共 $N$ 个。Alice 和 Bob 两位玩家轮流行动，Alice 先手。每人每次可以从堆中取走 $1$ 到 $m$ 个石子。取走最后一个石子的一方获胜。假设双方都采取最优策略，判断先手能否必胜。

解题思路

这是最基础、最经典的公平组合博弈模型——巴什博弈 (Bash Game)。

这类问题的核心是寻找游戏中的“必胜态”与“必败态”。一个局面是“必败态”，指的是无论当前玩家如何操作，都会将一个“必胜态”留给对手。反之，如果一个局面至少存在一种走法，能够将“必败态”留给对手，那么这个局面就是“必胜态”。

寻找关键局面 让我们思考一个特殊情况：如果当前石子数量为 $m+1$ ，轮到你操作，会发生什么？
- 你必须取走 $k$ 个石子，其中 $1 \le k \le m$ 。
- 取完后，剩余的石子数量为 $(m+1) - k$ ，这个数量的范围是 $[1, m]$ 。
- 此时，你的对手面对 $1$ 到 $m$ 个石子，他可以一次性将它们全部取走，从而获胜。
- 因此，当石子数量为 $m+1$ 时，轮到的玩家必输。这是一个关键的必败态。
推广规律 既然 $m+1$ 是一个必败态，那么双方的最优策略就是尽可能地将这个局面（或其倍数）留给对方。
- 当 $N$ 不是 $m+1$ 的倍数时：设 $N = q \cdot (m+1) + r$ ，其中 $1 \le r \le m$ 。先手 Alice 可以非常聪明地只取走 $r$ 个石子。这是一个合法的操作，因为 $1 \le r \le m$ 。操作后，剩下 $q \cdot (m+1)$ 个石子。现在轮到 Bob，他面对的是一个 $m+1$ 的倍数。
- 当 $N$ 是 $m+1$ 的倍数时：设 $N = q \cdot (m+1)$ 。先手 Alice 必须取走 $k$ 个石子，其中 $1 \le k \le m$ 。操作后，剩下 $N-k$ 个石子，这个数量显然不再是 $m+1$ 的倍数。现在轮到 Bob，他面对的就是上面一种情况。Bob 同样可以取走余数，将一个更小的 $m+1$ 的倍数还给 Alice。
最终结论 这个过程不断重复。如果初始石子数 $N$ 是 $m+1$ 的倍数，那么 Alice 每次都会破坏这个倍数关系，而 Bob 总能将其修复。最终，Alice 将会面对 $m+1$ 个石子并输掉比赛。反之，如果初始 $N$ 不是 $m+1$ 的倍数，Alice 就能在第一步掌控主动权，迫使 Bob 总是面对 $m+1$ 的倍数。
- 如果 $N \pmod{m+1} = 0$ ，则先手必败（Bob 胜）。
- 如果 $N \pmod{m+1} \neq 0$ ，则先手必胜（Alice 胜）。

代码

cpp
java
python

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n % (m + 1) == 0) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            if (n % (m + 1) == 0) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
    }
}

import sys

def solve():
    t_str = sys.stdin.readline()
    if not t_str:
        return
    t = int(t_str)
    for _ in range(t):
        line = sys.stdin.readline()
        if not line:
            break
        n, m = map(int, line.split())
        if n % (m + 1) == 0:
            print("NO")
        else:
            print("YES")

solve()

算法及复杂度

算法: 博弈论 (巴什博弈)
时间复杂度: 对于每组测试数据，我们只进行了一次取模和判断操作，时间复杂度为 $\mathcal{O}(1)$ 。总的时间复杂度为 $\mathcal{O}(T)$ ，其中 $T$ 是测试数据的组数。
空间复杂度: 没有使用额外的存储空间，空间复杂度为 $\mathcal{O}(1)$ 。