基础

概念

• 不能操作者输的游戏是 Normal，不能操作者赢的游戏是 Misère。
• 转移状态不存在环的情况的游戏是 Normal，存在环的游戏叫做 Loopy。
• 操着至与场上状态有关的是平等游戏，于操作的人有关的是不平等游戏。

基础博弈

例题 $1$

有一张有向无环图，图上有一枚棋子。双方轮流操作，每次操作可以将棋子沿着当前点的 一条出边移动。不能操作者输，求获胜方。

定义 $f_i$ 表示在节点 $i$ 是否有必胜策略，显然在出度为 $0$ 的节点如果先手操作那么注定失败。

否则如果 $\exists j\in \operatorname{successor node}(i)\wedge f_j=0$，那么在 $i$ 号节点操作时就可以将棋子推向 $j$，所以 $f_i=1$。

反之如果 $\forall j\in \operatorname{successor node}(i)\wedge f_j=1$，那么无论推向哪里都是另一个人必胜，那么可以得到 $f_i=0$。

例题 $2$

有一张有向图，图上有一枚棋子。双方轮流操作，每次操作可以将棋子沿着当前点的 一条出边移动。不能操作者输，求获胜方。

因为现在的图是有环的，所以游戏可能永远都不会结束，显然不可以直接通过上面的方法求解。

定义 $f_i$ 表示在 $i$ 节点是否有必胜策略，特别的如果平局那么 $f_i=\texttt{?}$。

对于例题 $1$ 的分析显然还是成立的，所以我们可以求解出一部分的 $f_i$ 的值，对于其他的情况必然满足 $f_i=\texttt{?}$，证明如下：

显然 $f_i\ne 1$，因为 $i$ 节点一定满足 $\forall j\in \operatorname{successor node}(i)\wedge f_j\ne 0$，所以 $f_i=0$ 或者 $f_i=\texttt{?}$，显然在失败与平局面前玩家肯定会选择平局。

应用

对于所有的公平博弈我们都可以将场面看作节点，将操作看成边抽象成上面的两种博弈。同样的，对于不公平博弈，我们也可以将操作的人与场上的状态一起抽象成节点。

但是显然将所有的状态全部枚举并不实际，所以我们往往需要进行规律的寻找与优化。

【AGC002E】 Candy Piles

题目大意

有 $n$ 堆糖，第 $i$ 堆有 $a_i$ 个。有两个人轮流进行一下操作：

1. 将当前最大的那一堆吃完。
2. 吃所有还有糖的糖堆中的一颗糖。

率先吃完所有糖的人输，求谁有必胜策略。

其中数据范围满足，$1\le n\le 10^5,1\le a_i\le 10^9$。

思路

抽象一下操作，其实就是删除左边一行或者下面一列。

可以将所有的操作抽象成网格图。

对于任意一个不在边界上的点，如果它的上面和右面都是必败点，那么这个点一定是必胜点。如果它的上面和右面有一个是必胜点，那它就是必败点。

因为从原点 $(0,0)$ 出发，所以当原点是必胜点时，后手必胜；原点是必败点时，先手必胜。

将整个网格图构造出来复杂度太大，所以考虑找规律：

除了边界外，同一对角线上的点全部是相同类型的点。

我们可以通过算出原点最右上方且不在边界上的点的类型，来知道原点是必胜点还是必败点。

找到以原点为左下角的最大正方形，设其右上方顶点为 $(i,i)$ 。当它到最上面且不在边界上的点的距离和最右面且不在边界上的点的距离其中一个为奇数时，这个点为必败点，反之这个点为必胜点。

Submission #55712942 - AtCoder Grand Contest 002

Choosing Carrot

题目大意

给你一个序列，A 和 B 一次轮流操作，A 希望答案剩余的最大，B 希望答案最小，但是所有的操作都需要满足操作实在端点。

对于 $\forall k\in[1,n]\cap \mathbb{Z}$ ，重新开始一局游戏，A 先在满足要求的情况下选取 $k$。

其中数据范围满足，$1\le n\le 3\times 10^5$。

思路

某大佬曾经说过，如果一方用一个简单的操作就能达到某种结果，那他的最终结果不会更差。

对于权值博弈则可以延申为：如果先手能保证不小于某个值，后手能保证不大于某个值，那么答案就是这个。

定义 $mid=\lfloor \dfrac{1+n}{2}\rfloor$，那么对于 $k=0$ 的情况，答案的取值如下：

$ans=\left\{\begin{matrix} \max(a_{mid},a_{mid+1}) & n\text{ is even}\\ \max(\min(a_{mid},a_{mid-1}),\min(a_{mid},a_{mid+1})) & n\text{ is odd} \end{matrix}\right.\mathbb{}$

先证明 $n$ 是偶数是的正确性：

首先 A 可以选择 $a_{mid},a_{mid+1}$ 中最大值的位置 $p$ 与 $1,n$ 中距离较远的位置选择，接着和 B 进行对称的操作，这样就可以保证在选择了 $n-2$ 次只剩 $a_{p-1},a_p$ 或者 $a_p,a_{p+1}$。

接着 A 只需要选择 $a_{p-1}$ 或者 $a_{p+1}$ 就一定可以剩余 $a_p$。

根据某个某个大佬总结的性质，因为 A 可以将答案牢牢控制在 $a_p$，所以这一定是最优解。

再证明 $n$ 是奇数的情况的正确性：

首先 A 可以选择 $a_1$ 或者 $a_n$，那么问题就转化为了 $n$ 是偶数的情况，区别只有 B 希望答案更小。

同样的，B 可以使用上面的方法将最后的取值控制在 $\min(a_{mid'},a_{mid'+1})$，其中 $mid'$ 为 A 选择后中间的位置。

容易得到 $mid'=mid$ 或 $mid'=mid-1$，所以答案就是 $\max(\min(a_{mid},a_{mid-1}),\min(a_{mid},a_{mid+1}))$。

对于 $k\ne 0$ 的情况，容易想出 A 率先吃肯定只有 $mid$ 的值会受到影响，考虑计算出每一个 $k$ 可以影响的 $mid$ 的取值取值范围。

对于 $k$ 个全部取在左边的情况，$mid=\lfloor \dfrac{n-k+1}{2}\rfloor+k$ 。

同理对于 $k$ 全部取在右边的情况，$mid=\lfloor \dfrac{n-k+1}{2}\rfloor$。

设 $x=\lfloor \dfrac{n-k+1}{2}\rfloor$，那么答案为：

$\left\{\begin{matrix} \max \limits _{{\tiny i=\lceil \dfrac{n-k}{2}\rceil }}^{{\tiny \lceil \dfrac{n+k}{2}\rceil}} a_i& n-k\text{ is odd}\\ \max \limits_{{\tiny i=\lfloor \dfrac{n-k}{2}\rfloor -1}}^{{\tiny \lfloor \dfrac{n+k}{2}\rfloor}} (\min(a_{i},a_{i+1}))&n-k\text{ is even} \end{matrix}\right.$

另外 $k=n-1$ 的情况需要特判，应为在 A 拿完之后游戏就直接结束了，所以答案为 $\max\limits_{i=1}^{n}a_i$。

Submission #273106358 - Codeforces