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

题解：BISHI36 【模板】扩展巴什博弈

题目链接

题目描述

有一堆石子，双方轮流取走石子。设初始石子数为 $N$ ，每次必须取走 $L$ 到 $R$ 颗（含端点）。若某时刻剩余石子少于 $L$ 则无法行动，该玩家失败；拿到最后一颗者获胜。给出多组 $(N,L,R)$ ，判断先手是否必胜（YES/NO）。

解题思路

经典扩展巴什博弈（取走区间 $[L,R]$ ）。记 $f(N)$ 为先手在 $N$ 时是否必胜。可得败态呈现周期性：

结论：先手必败当且仅当 $N\bmod (L+R) < L$ ；否则先手必胜。

证明要点（简述）：将非负整数按长度为 $L$ 的“败段”和长度为 $R$ 的“胜段”交替划分，周期为 $L+R$ 。处于败段时，所有可达状态（减去 $[L,R]$ 中任意值）都落在后续的胜段；处于胜段时，总能选择恰当步数把对手送入败段。该结论与样例相符：

$N=3,L=5,R=7$ ： $3<L$ 无法行动， $3\bmod 12=3<L$ ，NO；
$N=9,L=2,R=4$ ： $9\bmod 6=3\ge 2$ ，YES；
$N=7,L=2,R=5$ ： $7\bmod 7=0<L$ ，NO。

代码

import java.io.*;

public class Main {
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        long nextLong() throws IOException {
            int c; long sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
        int nextInt() throws IOException { return (int) nextLong(); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();
        int T = fs.nextInt();
        while (T-- > 0) {
            long N = fs.nextLong();
            long L = fs.nextLong();
            long R = fs.nextLong();
            long rem = N % (L + R);
            out.append(rem < L ? "NO" : "YES").append('\n');
        }
        System.out.print(out.toString());
    }
}

#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, L, R;
        cin >> N >> L >> R;
        long long period = L + R;
        long long rem = N % period;
        cout << (rem < L ? "NO" : "YES") << '\n';
    }
    return 0;
}

T = int(input())
for _ in range(T):
    N, L, R = map(int, input().split())
    print("NO" if (N % (L + R)) < L else "YES")

算法及复杂度

算法：周期类减法博弈；判断 $N\bmod (L+R)$ 是否小于 $L$
时间复杂度： $\mathcal{O}(T)$
空间复杂度： $\mathcal{O}(1)$