POJ 1067/洛谷 P2252 取石子游戏 题解【博弈】【威佐夫博弈】

点击量：206

    最基础最裸的威佐夫博弈。

目录

题目描述

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

输入输出格式

输入格式：

输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数\(a\)和\(b\)，表示两堆石子的数目。

输出格式：

输出对应也有若干行，每行包含一个数字\(1\)或\(0\)，如果最后你是胜者，则为\(1\)，反之，则为\(0\)。

输入输出样例

输入样例#1：

2 1
8 4
4 7

输出样例#1：

0
1
0

说明

\(a,b\le 1,000,000,000\)

题解：

    威佐夫博弈的题面就是这样，有两堆石子，要么只取一堆，要么两堆取一样多。

    定义先手必输的局势为“奇异局势”。那么可以列举出前几个奇异局势：\((0,0),(1,2),(3,5),(4,7),…\)。而后面的单纯靠找是很难找到的，不过可以发现规律，设奇异局势中\((x,y)\)满足\(x<y\)，可以看出，\(x\)是当前没有出现过的最小非负整数。因此在威佐夫博弈里，每一个自然数会且仅会出现在奇异局势中一次。

    设第\(i\)个奇异局势的\(x,y\)分别为\(x_i,y_i\)，那么可以发现，如果把\((0,0)\)当作第\(0\)个奇异局势，那么总满足\(y_i=x_i+i\)。

    可以发现，非奇异局势总能被转化为奇异局势。因为\(y_i-x_i=i\le x_i\)，如果两个数相对差较小，为\(k\)，要调整到奇异局势就要把两个数较小的那个调整到\(x_k\)，而差值为\(k\)，较大的那个自然就是\(y_k\)了。

    举个例子，对于局势\((12,13)\)，\(13-12=1\)，它们同时减去\(11\)，得到\(1,2\)，是一个奇异局势；如果两个数相对差较大，那么较大的数通过做减法一定可以变成较小数在奇异局势中的另一半。比如\((5,12)\)，发现\(12-5=7\)，在\(5\)以下不可能出现差为\(7\)的奇异局势，但是发现\(12\)可以被调整为\(3\)，这样就产生了奇异局势。

    可以认为，如果当前局势为\((x,y)\)，若存在奇异局势\((x_i,y_i),x_i\le x\)，\(i>(y-x)\)，就存在\((x_{i’},y_{i’})\)刚好满足\(i’=(y-x)\)。若不存在，就说明\(y-x>i\)，存在一个奇异局势，\(x_i=x\)或者\(y_i=x\)，如果\(x_i=x\)，那么\(y_i=x_i+i=x+i<y\)，把当前局势的\(y\)调整为\(x+i\)就可以了；如果\(y_i=x\)，那么\(x_i=x-i<y\)，把当前局势的\(y\)调整为\(x-i\)，也可以得到奇异局势。

    如果上述条件都不满足，说明当前局势就是一个奇异局势，先手必败，就输了。

    先手通过改变非奇异局势来造成后手的奇异局势，此时后手已经没有办法再变成更小的奇异局势了，因为\(y-x\)和\((x,y)\)只能有一个被修改，只能得到非奇异局势。这时先手又可以把新出现的非奇异局势变成奇异局势。直到最后出现\((0,0)\)，后手输。

    其实威佐夫博弈可以套用公式，对于局势\((x,y),x<y\)，如果\((y-x)\times \frac{\sqrt{5}+1}2=x\)，那么这个局势\((x,y)\)就是一个奇异局势，先手必败。反之先手有必胜策略。

    吐槽，不要带黄金分割数\(1.618\)，精度不够……需要当场开根号或者存一个精度比较高的值……

Code：

#include<cstdio>
#include<cmath>
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n<m)//使n>m
        {
            int t=n;
            n=m;
            m=t;
        }
        if(floor((n-m)*((sqrt(5)+1)/2))==m)
            puts("0");
        else
            puts("1");
    }
    return 0;
}