威佐夫博弈（Wythoff Game）

简述

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

分析

我们用（$a_k，b_k$）（$a_k≤b_k,k=0，1，2，...,n$)表示两堆物品的数量并称其为局势，如果甲面对（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$ = k ∗（1 + sqrt(5)）/ 2，$b_k=a_k+k$，先手必败，否则先手必胜（详细证明过程可以看文章）。再抽象一点就是：有两堆物品的初始值为$(x,y)$,

且$x < y$，令$z = y – x$，记w = (int)[z * (sqrt(5) + 1)  /  2]，若w = x，则先手必败，否则先手必胜

例题

1.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;
}

参考文章：https://hrbust-acm-team.gitbooks.io/acm-book/content/game_theory/wei_zuo_fu_bo_yi.html