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

Louis_lxy · 2024-03-31 14:18:23 · 题解

参考了此文章。

首先，此题很多题解都使用了黄金分割，但是因为精度问题导致被 Hack，至于改进方法有两种，第一种，使用牛顿迭代法；第二种，重写求根函数，提高精度，第一种精度更高，但是第二种对新手更友好。

结论

首先，此题的结论如下：如果存在一个 w=\lfloor(b-a)*\frac{\surd 5+1}{2}\rfloor(a<b)，使得 w=a，那么后手必胜，也就是先手必败。

证明

证明过程是参考百度的证明过程，尽量写的简单一点。

首先，我们要知道什么叫奇异局势，以及它的性质。

满足以下条件的即为奇异局势：

1. 任何自然数都包含在一个且仅有一个奇异局势中。
2. 任意操作都可将奇异局势变为非奇异局势。

其中第二点就是为什么奇异局势一定保证后手必胜的关键。

那么，我们知道了所有的奇异局势都能保证后手必胜，难点就在于怎么判断奇异局势了。

首先，我们可以先枚举一下，找找规律。不要说这是纯粹打表找规律，很多题目都是先找到规律再证明的。

首先，第一个奇异局势是 (0,0)，很容易发现，它满足第二个性质（判断时只需要满足第二个性质即可），那么就有如下的表。

仔细观察即可发现，对于一个奇异局势，它的编号为 n 时，n=b-a，但是继续枚举可以发现，a 的变化没什么规律，时而加一时而加二。

那么这里就要用到 Betty 定理。

Betty 定理如下：

如果有两个无理数 a，b 满足 \frac{1}{a}+\frac{1}{b}=1，那么有如下性质：对于两个集合 A，B，满足：A=\{ \lfloor an\rfloor\}，B=\{ \lfloor bn\rfloor\}，n\in Z+，同时存在如下结论 A\cap B=\phi，A\cup b=Z+。

有了 Betty 定理，那么就有如下证明：

对于一个奇异局势，根据 Betty 定理，a 可以被表示为 \lfloor an\rfloor，则 b 可以表示为 \lfloor an\rfloor+n=\lfloor (a+1)n\rfloor，则：

所以第 n 个奇异局势就是：\lfloor\frac{\surd 5+1}{2}n,\frac{\surd 5+1}{2}n+n\rfloor，那么代码就很容易写出来了：

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int a, b, ans;
    cin >> a >> b;
    ans = abs(a - b) * ((sqrt(5) + 1) / 2.0);
    if (ans == min(a, b))
            cout << 0;
    else
            cout << 1;
}

但是交上去会发现 WA 了两个点，那就是此题的 Hack 数据。

优化

分析后可得，WA 的原因是 double 的精度不够，而 \operatorname{sqrt} 函数的返回值是 double，所以有两种方法，牛顿迭代法和重写 \operatorname{sqrt} 函数。这里主要讲重写 \operatorname{sqrt} 函数的方法。

首先，我们要知道，想要直接求出数值是很难的那么就有一种很实用的方法：二分。

首先，定义一个 l 和一个 r，表示上界和下界，l=0，r=10^{100}，当然 r 赋值成一个极大值即可，这里偷一下懒直接赋值成 10^{100}，反正 long double 存的下。

然后对于每次二分，取一个平均值 mid，然后判断如果 mid^2 \le n 那么 l \gets mid，反之 r \gets mid。注意，实数二分不能用 l<r 这个判断！不然会死循环。应写成：r-l>所需精度，而这道题想要不被 Hack，精度至少要开到 10^{-16}，由于要防止再次被 Hack，我开到了 10^{-18}，最后返回 l 即可。

另外再额外提一种优化，时间复杂度 O(n)，但也可以通过，就是牛顿迭代法。

具体来讲，只要将一个数 s 赋值成 \sqrt n，然后对这个数进行 n 次操作，每次将 s\gets n/s，不断循环往复，最终就能得到精度足够的答案，具体证明可以看这篇文章。

证明过程：

AC CODE

1.重写求根函数

#include <iostream>
using namespace std;

long double sqrt(long double n)
{
    long double l = 0, r = 1e100;
    while (r - l > 1e-18)
    {
        long double mid = (l + r) / 2;
        if (mid * mid <= n)
            l = mid;
        else
            r = mid;
    }
    return l;
}

int main()
{
    long long a, b, ans;
    cin >> a >> b;
    ans = abs(a - b) * ((sqrt(5) + 1) / 2.0L);
    if (ans == min(a, b))
        cout << 0;
    else
        cout << 1;
}

2.牛顿迭代法

#include <iostream>
#include <math.h>
using namespace std;

long double Sqrt(long double n)
{
    long double s = sqrt(n);
    for (int i = 1; i <= n; ++i)
        s = n / s;
    return s;
}

int main()
{
    long long a, b, ans;
    cin >> a >> b;
    ans = abs(a - b) * ((Sqrt(5) + 1) / 2.0L);
    if (ans == min(a, b))
        cout << 0;
    else
        cout << 1;
}