问题 C: 为美好的世界献上爆炎（博弈论）

题目描述

在红魔村中，悠悠向惠惠发起了挑战。

桌上有 n 枚硬币，两人轮流拿硬币。每次可以在区间 [l, r] 中选择一个数字 x 然后拿走 x 枚硬币，若一方无法再拿取则输掉了游戏，由惠惠先手开始拿硬币。

惠惠和悠悠都是聪明的，现在惠惠想在游戏开始前，请你帮忙判断她是否能够必胜，若她可以必胜则会按照必胜策略和悠悠进行游戏，若不能必胜她就只好作弊来战胜悠悠了。

游戏一共会进行 t 局，每局游戏都需要你判断胜负。

输入

第一行包含一个正整数 t ，表示有 t 局游戏。

接下来 t 行每行三个正整数 n, l, r ，表示有硬币数量 n 和区间 [l,r] 。

输出

输出 t 行，每行输出 yes 或 no，yes 表示本局惠惠可以必胜，no 表示本局惠惠不可以必胜。

样例输入 Copy

2
6 1 4
10 3 5

样例输出 Copy

yes
no

提示

对于 30% 的数据，满足 l = 1 。

对于另 20% 的数据，满足 n≤500, t≤ 500 。

对于另 20% 的数据，满足 n <= 5000, t≤ 5000 。

对于 100% 的数据，满足 1≤ l≤ r≤ n <= 109, t≤ 105 。

deepsleep答案：

核心思路是分析游戏的 必胜态 和 必败态 ，并利用周期性优化计算（因为 n 很大，无法动态规划）。 

必败：当前玩家无法行动，或无论怎么行动，对手都能获胜。

必胜：当前玩家可以强制获胜。

• 当 l ≤ n ≤ r 时，玩家可以一次性取完所有硬币，直接获胜，是必胜态。

• 当 n > r 时，玩家可以取 x 枚（x ∈ [l, r]），使剩余硬币数为 n - x。目标是将对手逼入必败态。

• 游戏状态（赢/输）以周期 s = l + r 重复。

必败的条件：n < l 或 n % (l + r) < l。

必胜的条件：n ≥ l 且不满足必败态条件。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,l,r;
int main(){scanf("%lld",&t);while(t--){scanf("%lld%lld%lld",&n,&l,&r);if(n<=r){printf("yes\n");continue;}n%=(l+r);if(n<l)printf("no\n");else printf("yes\n");	}return 0;
}