题解：P2252 [SHOI2002] 取石子游戏|【模板】威佐夫博弈

· · 题解

推销文章：博弈论半家桶-从入门到门入从

有两堆石子，石子数可以不同。两人轮流取石子，每次可以在一堆中取，或者从两堆中取走相同个数的石子，数量不限，取走最后一个石头的人获胜。判定先手是否必胜。

威佐夫博弈不同于 Nim 游戏与 Bash 博弈，它的特殊之处在于不能将两堆石子分开分析。

证明可以不看的 www。

因为只有两堆石子，先进行一步转化给他丢到二维坐标系上，那么坐标 (x,y) 就表示两堆的石子数量。

我们考虑观察性质，我们可以枚举几个必败状态，例如 (0,0),(1,2),(3,5),(4,7),\dots

我们观察状态，可以发现两个规律，我们假设从小到大排的第 k 个必败状态是 (x,y)，并且 x<y。并且我们发现 y=x+k。这个说明的就是必败状态两个数的差值是递增的，所以也就说明了每一个必败状态的差值都各不相同。证明我们待会在来看。

那么原来的问题，我们可以把游戏转化为，棋盘上有一个点，每个人可以将棋子往下，向左或向左下移动若干的棋子，不能移动的人。能够一步移动到原点的点显然就是必胜点，假设我们给这些所有必胜点都染色的话，剩下的的没当中横纵坐标和最小的点就是下一个必败点，因为无论如何移动都会给对手留下一个必胜点。

我们借用梁唐的知乎博客的图，将必败点染色刻画可以得到如下图：

从图中不难看出，必败点之间是无法一次移动就能得到的，换句话说可以一次移动到必败点的点都是必胜点，那么上图中除了必败点之外的点都是必胜点，并且每一个自然数必然只会被包含在一个必败状态之中。

那么根据图的一些奇妙性质，我们定义，先手必输的局势为奇异局势。不妨设 (x,y) 为第 k 个奇异局势。那么有如下性质：

第一个，考虑反证法，假设 (a,a+k),(b,b+k) 是必败状态，并且 a<b。那么先手面临 (b,b+k) 的时候，只需要在两堆当中同时取走 b-a 个石子，那么给后手的局面就是 (a,a+k)。但是对于后手来说，这是一个必败的局面，那么 (b,b+k) 不就是必胜状态了吗，矛盾，所以不存在两个必败局面的差值相等。

第二个个证明考虑反证法，我们需要证明两点：

  1. 任意自然数都出现过。
  2. 任意自然数只出现一次。

证明如下：

  1. 反证法，如果 v 没有出现过，那么 v 显然可以做一个新奇异局势的 x。
  2. 反证法，假设 v 出现了两次，那么 v 一定不是所在奇异局势的 x，那么 v 只能同时是两个奇异局势的 y，但因为任意一个奇异局势的差值不相同，所以 v 不可能存在。

第三个，我们考虑若取走一堆中的石子，那么两对石子的差值会改变，必将成为非奇异局势。若同时取走，因为同一个差值只会对应一种奇异局势，必将成为非奇异局势。

第四个是显然的，不证明。

那么现在问题在于我们如何快速找出一个通项公式使得对于第 k 个必败局面，它的坐标是 (x_{k},y_{k}) 呢？

我们有 Betty 定理！

设 a,b 是两个正无理数，且 \dfrac{1}{a}+\dfrac{1}{b}=1。 记 P=\left\{ \lfloor a\times n \rfloor|n \in \mathbb{N}^{+} \right\},Q=\left\{ \lfloor b\times n \rfloor|n \in \mathbb{N}^{+} \right\}，则 P \cap Q=\varnothing,P \cup Q =\mathbb{N}^{+}。

证明可以去网上看。

那不对啊，我们是自然数你这是无理数，你这八杆子打不着的东西拿出来用干啥啊。因为我们发现必败状态的通项和 Betty 定理序列很像，具体哪里像可以继续看啦。

我们不妨假设存在这样的 a,b 同时满足 Betty 定理和必败状态的性质，当然无理数不可能作为坐标出现啦，我们当然要让它变为整数。

那怎么办，Betty 有一个推论就是：

任何正整数都可刚好以一种形式表示为不大于其中一个无理数的正整数倍的最大整数。

从定理直接推，那么有如下式子：

\begin{cases} \lfloor a\times n\rfloor +n = \lfloor b\times n \rfloor \\ \frac{1}{a}+\frac{1}{b}=1 \end{cases}

解第一个方程：

\begin{aligned} \lfloor b\times n \rfloor & = \lfloor a\times n\rfloor +n \\ & = \lfloor a\times n +n \rfloor \\ & = \lfloor (a+1) \times n\rfloor \\ \therefore b &= a+1 \end{aligned}

那么代入第二个方程有：

\frac{1}{a}+\frac{1}{a+1}=1

开解！

\begin{aligned} & \frac{1}{a} + \frac{1}{a+1} = 1 \\ & \frac{1}{a} =\frac{a+1}{a(a+1)} \\ & \frac{1}{a+1} = \frac{a}{a(a+1)} \\ & \therefore \frac{a+1}{a(a+1)}+\frac{a}{a(a+1)}=1 \\ & \to \frac{2a+1}{a(a+1)}=1 \\ & \therefore 2a+1=a(a+1)=a^2 +a \\ & \therefore 2a+1-a^2 -a =0 \\ & \therefore a^2-a-1=0 \end{aligned}

利用初中知识不难得出 a=\dfrac{1+\sqrt{5}}{2} 或 \dfrac{1-\sqrt{5}}{2}。

完了吗？敢说完了的扣 114514 分 (≧m≦)

设 a,b 是两个正无理数，且 \dfrac{1}{a}+\dfrac{1}{b}=1。

正无理数！所以解为 a=\dfrac{1+\sqrt{5}}{2}。

综上，假设两堆石子为 (x,y),x<y。

那么先手必败，当且仅当：

(y-x) \times \frac{\sqrt{5}+1}{2}=x

其中，\dfrac{\sqrt{5}+1}{2} 就是黄金分割数，很神奇的。

题目：P2252

#include<bits/stdc++.h>
#define double long long
using namespace std;
const double hjfg=((1.0+sqrt(5.0))/2.0);
double a,b;

int main(){
    cin>>a>>b;
    if(a>b) swap(a,b);
    double ans=(b-a)*((1.0+sqrtl(5.0))/2.0);
    if(ans==a) cout<<0;
    else cout<<1;
    return 0;
}