题解 | #【模板】扩展巴什博弈#
【模板】扩展巴什博弈
https://www.nowcoder.com/practice/4b0d36a3d3884cf69f618cf4c2511d82
题解：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")
算法及复杂度
- 算法：周期类减法博弈；判断
是否小于
- 时间复杂度：
- 空间复杂度：
查看2道真题和解析