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

题目链接

题目描述

有一堆石子，共 $N$ 个。Alice 和 Bob 两位玩家轮流行动，Alice 先手。每人每次可以从堆中取走 $k$ 个石子，其中 $m_1 \le k \le m_2$ 。如果轮到某位玩家时，剩余石子数小于 $m_1$ ，则该玩家无法操作，判负。取走最后一个石子的一方获胜。假设双方都采取最优策略，判断先手能否必胜。

解题思路

本题是巴什博弈的扩展形式。标准的巴什博弈允许取 $[1, m]$ 个石子，而本题允许取 $[m_1, m_2]$ 个。解题的核心思想仍然是寻找游戏状态的周期性，并划分出周期内的“必胜态”与“必败态”。

寻找状态周期 通过博弈论的归纳分析可以证明，此类取石子游戏的胜负状态是以 $m_1 + m_2$ 为周期循环的。也就是说，一个有 $N$ 个石子的局面，其胜负性质等同于一个有 $N \pmod{m_1 + m_2}$ 个石子的局面。
划分周期内的必败态 在一个周期内，即石子数 $n$ 满足 $0 \le n < m_1 + m_2$ 时，我们需要确定哪些是必败态。
- 根据规则，如果轮到某个玩家时，石子数小于 $m_1$ ，该玩家就无法行动，直接判负。
- 因此，石子数在区间 $[0, m_1-1]$ 内的局面都是必败态。
划分周期内的必胜态
- 如果一个局面 $n$ 允许玩家通过一次操作（取 $k$ 个石子）将局面转移到一个必败态 $n-k$ ，那么局面 $n$ 就是一个必胜态。
- 对于区间 $[m_1, m_1+m_2-1]$ 内的任何局面 $n$ ，玩家总可以找到一个合法的取石子数量 $k$ (其中 $m_1 \le k \le m_2$ )，使得剩余的石子数 $n-k$ 落在必败区间 $[0, m_1-1]$ 中。因此，这些局面都是必胜态。
最终结论 结合以上两点，我们可以得到一个简单的判断法则：
- 首先计算 $N$ 在一个周期内的等效状态： $r = N \pmod{m_1 + m_2}$ 。
- 然后判断这个等效状态 $r$ 是否落在必败区间内。
- 如果 $r < m_1$ ，则初始局面 $N$ 是一个必败态，先手必败（Bob 胜）。
- 如果 $r \ge m_1$ ，则初始局面 $N$ 是一个必胜态，先手必胜（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--) {
        long long n, m1, m2;
        cin >> n >> m1 >> m2;
        
        long long r = n % (m1 + m2);

        if (r >= m1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        String tStr = br.readLine();
        if (tStr == null) return;

        int t = Integer.parseInt(tStr);
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long n = Long.parseLong(st.nextToken());
            long m1 = Long.parseLong(st.nextToken());
            long m2 = Long.parseLong(st.nextToken());
            
            long r = n % (m1 + m2);

            if (r >= m1) {
                out.println("YES");
            } else {
                out.println("NO");
            }
        }
        out.flush();
        out.close();
    }
}

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, m1, m2 = map(int, line.split())

        r = n % (m1 + m2)

        if r >= m1:
            print("YES")
        else:
            print("NO")

solve()

算法及复杂度

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