ACM博弈论总结

一、Bash博弈

1、问题模型：只有一堆n个物品，两人轮流从这堆物品中取物，最多取m个，最后取光者胜。

2、解决思路：当n=m+1时，由于一次最多取m个，无论先取者拿走多少个，后取者都能一次拿走剩余的物品，后者取胜，所以当一方面对n%(m+1)==0的时候，其面临的是必败局势。所以当n==(n+1)*r+s（r为任意自然数，s<=m）时，如果先取者要拿走s个物品，后取者拿走x（x<=m）个物品，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保留给对手留下（m+1）的倍数，就能最后获胜。

3、变形：条件不变，改为最后取光的人输。

解决方法：当(n-1)%(m+1)==0时，后手胜利。

例题：Bash的游戏

#define _MAX 10000

int a[_MAX];

int b[_MAX];

int bash(int N, int K)

{

    if (N % (K + 1) == 0)

    {

        return 2;

    }

    return 1;

}

int main()

{

    int T;

    scanf("%d", &T);

    for (int i = 0; i < T; i++)

    {

        scanf("%d%d", a + i, b + i);

    }

    for (int i = 0; i < T; i++)

    {

        if (bash(a[i], b[i]) == 1)

        {

            printf("A\n");

        }

        else

        {

            printf("B\n");

        }

    }

    return 0;

}

二、威佐夫博弈

1、问题模型：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆取出同样多的物品，规定每次取出一个，多者不限，最后取光者得胜。

2、解决思路：A:设（ai,bi）(ai<=bi,i=0,1,2,3.....,n)表示两堆物品的数量并称其为局势，如果甲面对（0,0）,那么甲输了，这种局势我们称为其一局势。

奇异局势的前几项是：(0,0)、(1,2)、（3,5）、（4,7）、（6，10）、（8,13）、（9,15）、（11,18）、（12,20）

任给一个局势(a,b),如下公式判断它是不是奇异局势：

ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数）。（证明见百度百科）也就是黄金分割点。

3、满足上述公式的局势性质：

（1）任何自然数都包含在一个且仅有一个奇异局势中。

（2）任何操作都可以把奇异局势变为非奇异局势。

若只改变奇异局势（ak,bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。

（3）采用适当的方法，可以将非奇异局势变为奇异局势。

假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b – bk个物体，即变为奇异局势；如果 a = ak ， b < bk ,则同时从两堆中拿走 ak – ab – ak个物体,变为奇异局势（ ab – ak , ab – ak+ b – ak）；如果a > ak ，
b= ak + k,则从第一堆中拿走多余的数量a – ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，a=aj （j < k）,从第二堆里面拿走 b – bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b – aj 即可。

4、结论

两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，后拿者必胜。

例题：威佐夫博弈

int main()

{

    int t, a, b, m, k;

    scanf("%d", &t);

    while (t--)

    {

        scanf("%d%d", &a, &b);

        if (a > b)

        {

            a ^= b;

            b ^= a;

            a ^= b;

        }

        m = b - a;

        k = (int)(m * (1 + sqrt(5)) / 2.0);

        //m = ? * a

        //k = m / ?

        //?:黄金分割数

        //如果a == k，则为后手赢，否则先手赢（奇异局）

        printf("%s\n", a == k ? "B" : "A");

    }

    return 0;

}

威佐夫博弈 V2（大数）

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

using namespace std;

typedef long long LL;

LL tmp[3] = {618033988,749894848,204586834};

LL MOD = 1000000000;

int main()

{

    int T;

    LL m, n;

    cin>>T;

    while(T--)

    {

        cin>>m>>n;

        if(m < n)

            swap(n, m);

        LL cha = m - n;

        LL ta = cha/MOD, tb = cha%MOD;

        LL tp = tb*tmp[2];

        tp = ta*tmp[2] + tb*tmp[1] + tp/MOD;

        tp = ta*tmp[1] + tb*tmp[0] + tp/MOD;

        tp = cha + ta*tmp[0] + tp/MOD;

        if(tp == n)

            puts("B");

        else

            puts("A");

    }

    return 0;

}

三、Nim博弈

1、问题模型：有三堆各若干个物品，两个人轮流从某一堆取人一多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

2、解决思路：

用（a,b,c）表示某种局势，显然(0,0,0)是第一种局势，无论谁面对奇异局势，都必然失败。

第二种是（0，n,n），只要与对手拿走一样多的物品，最后都将导致(0,0,0)。

搞定这个问题必须把必败态炸出：（a,b,c）是必败态等价于a^b^c==0（^表示异或运算）

3、推广：

如果我们面对的是一个非奇异局势(a,b,c),那么如何变成奇异局势呢？

假设a<b<c,我们只要将c变成a^b即可，因为a^b^(a^b)=(a^a)^(b^b)=0^0=0。要将c变成a^b，只要c-(a^b)。

例题：Nim的游戏

int main(int argc, const char * argv[])

{

    int N, stone, tag = 0;

    scanf("%d", &N);

    while (N--)

    {

        scanf("%d", &stone);

        tag ^= stone;

    }

    //tag为0则为后手赢，否则为先手赢

    printf("%c\n", tag == 0 ? 'B' : 'A');

    return 0;

}

巴特西