博弈问题

假设法

利用了一个公平组合游戏局面不是先手必胜就是先手必败，那么就可以假设一个局面是先手必胜还是先手必败，思考其决策。

在本题中，发现无论出去 1 后的局面是先手必胜还是先手必败，都可以通过相应的决策使得初始局面时先手必胜。

例题：2024.7.9T1

博弈论DP

就是从终态往前推

EX4 - Game on Sum

Hard Version、Easy Version

题面

Alice 和 Bob 正在玩一个游戏，游戏分为 n 个回合，Alice 和 Bob 要轮流对一个数 x 进行操作，已知这个数初始值是 0。

具体每个回合的行动规则如下：

1. Alice 选择一个在区间 [0,k] 之间的实数 t。
2. Bob 可以选择让 x 变成 x+t 或者 x−t，但是 Bob 在 n 个回合之内至少选择 m 次让 x 变成 x+t。

Alice想让最终的 x 最大，Bob 想让最终的 x 最小。

已知双方均采用最优策略，求最终的 x 值（对 10^9+7 取模）。

数据范围保证：1≤m≤n≤2000,k≤10^9+7。

题解

CF1628D2 Game on Sum (Hard Version) - 洛谷专栏 (luogu.com.cn)

Alice先走，Bob后走其实就是让最小值最大。

打表看结论

并且博弈论问题如果不是用 DP，那一定是找结论。且数据范围很大时——\(\mathcal O(N)\)，一定是找结论。与其观察什么时候先手必胜，不如观察什么时候先手必败，

例题：Caught in the Middle

打表发现先手必败当且仅当 R 与 L 括号匹配。证明方法与 NIM 博弈相同，分为可以到必败态与只能到必胜态。