博弈专题

巴什博弈：

一堆n个物品，两人轮流取，最少1个，最多m个，最后取光者胜

结论： if(n%(m+1) == 0) 先手必败   else 先手必胜

推广：

只有一堆n个物品，两个人轮流从中取物，规定每次取数区间[s,m]，当然如果少于s那么必须一次取完，最后取光者为胜。

结论：如果 0<n%(s+m)<=s 后手获胜

poj 2897

#include<bits/stdc++.h>
using namespace std;

int n,m,s;

int main()
{
    while(~scanf("%d%d%d",&n,&s,&m))
    {
        if(n % (m + s) > 0 && n % (m + s) <= s)
            printf("LOST\n");
        else printf("WIN\n");
    }
    return 0;
}

Nim博弈：

三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

结论: 当石子堆数为n堆时，则推广为当对每堆的数目进行异或之后值为零是必败态

威佐夫博弈：

两堆物品，两人轮流取，要求（1）从其中一堆取至少一件物品，至多不限（2)从两堆中同时取相同件物品

最后取光者胜

结论：两堆(x,y),(x > y) 令z = y - x

如果w = x ，先手必败 else 先手必胜

poj 1527

#include<bits/stdc++.h>
using namespace std;

int n,m;

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int t = abs(n - m);
        if(min(n,m) == int(((sqrt(5) + 1) / 2) * t)) printf("0\n");
        else printf("1\n");
    }
    return 0;
}

斐波那契博弈：

1堆石子有n个（n>1）,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍，先取完者胜

结论：判断石子数是否为斐波那契数，若n = f（k），则先手必败。

在斐波那契数列中，f（i） = f（i - 1） + f （i - 2），所以很好证明f（i） <=  f（i-1）* 2.

Poj 2516

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll f[100000],n;

void init()
{
    f[1] = f[2] = 1;
    for(int i = 3;i <= 50; ++i)
        f[i] = f[i - 1] + f[i - 2];
}

int main()
{
    init();
    while(~scanf("%lld",&n))
    {
        if(!n) break;
        bool flag = 0;
        for(int i = 1;i <= 50; ++i)
            if(n == f[i])
            {
                flag = 1;
                break;
            }
        if(!flag) printf("First win\n");
        else printf("Second win\n");
    }
    return 0;
}