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

题目链接

【模板】扩展巴什博弈

题目描述

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

解题思路

经典扩展巴什博弈（取走区间 ）。记 为先手在 时是否必胜。可得败态呈现周期性：

  • 结论：先手必败当且仅当 ；否则先手必胜。

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

  • ： 无法行动，，NO；
  • ：，YES；
  • ：，NO。

代码

#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;
}

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());
    }
}

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

算法及复杂度

  • 算法：周期类减法博弈；判断 是否小于
  • 时间复杂度：
  • 空间复杂度：