威佐夫博弈（Wythoff Game）

简述

有两堆若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者胜

题解

我们用（$a_k,b_k$）表示两堆物品的数量并称其为局势，如果甲面对 （0,0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0,0）、（1,2）、（3,5）、（4,7）、（6,10）、（8.13）、（9,15）、（11,18）、（12,20）。可以看出： $a_0=b_0=0$, $a_k$是未在前面出现过的最小自然数, 而$b_k=a_k+k$

必胜态必败态

满足$a_k=\frac{k*1 + \sqrt{5}} {2}$

$b_k=a_k+k$，先手必败，否则先手必胜（详细证明过程可以看这篇文章）。再抽象一点就是：有两堆物品的初始值为(x,y)，且$x<y$$令z=y-x$，记

$$ w=(int)[z*(\frac{\sqrt{5}+1}{2})] $$

若$w=x$，则先手必败，否则先手必胜

题目链接：HDU1527 取石子游戏

题解

威佐夫博弈模板

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        int bb = min(a,b);
        int k = abs(a - b);
        int temp=(k * (1 + sqrt(5)) / 2);
        if(bb == temp)
            printf("0\n");
        else
            printf("1\n");
    }
    return 0;
}