基础博弈

ACM
评论

今天好好反省自己的博弈方面的欠缺。
这个博客讲解博弈比较全面。

（一）巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。
ans:保持给对手留下（m+1）的倍数，就能最后获胜。

巴什博奕例题：
HDU 1846/2188

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        puts(n%(m+1)?"first":"second");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        puts(n%(m+1)?"Grass":"Rabbit");
    }
}

hdu 2149

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include<stdio.h>
int main()
{
    int n,m;
    while(~scanf("%d%d",&m,&n))
    {
        if(m%(n+1)==0&&n<m)puts("none");
        else
        {
            if(n>=m)
                for(int i=m;i<=n;i++)
                printf("%d%c",i," \n"[i==n]);
            else printf("%d\n",m%(n+1));
        }
    }
}

变相巴什博奕：
HDU 1517/POJ 2505
起点：1
操作：乘 [2-9]中的一个数
情况分界：1-9 -9X2 - 9X2X9 ……..
先者掌握奇数局面 ，后者掌握偶数局面。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int c=1;
        while(c<n)
            c*=18;
        c/=18;
        if(c*9<n)puts("Ollie wins.");
        else puts("Stan wins.");
    }
}

（二）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
ans:面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
奇异局势：ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数)

HDU 1527

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include<stdio.h>
double k=(1+sqrt(5.0))/2;
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        if(n>m)swap(n,m);
        int ans=(int)(k*(m-n));
        if(n==ans)puts("0");
        else puts("1");
    }
}

（三）尼姆博奕（Nimm Game）：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
ans：
取火柴的游戏
题目1：今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
题目2：今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
题目1例题（Nim博弈）：
HDU 1849 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include<stdio.h>
int main()
{
    int n;
    int tp;
    while(scanf("%d",&n),n)
    {
        int ans=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&tp);
            ans^=tp;
        }
        puts(ans?"Rabbit Win!":"Grass Win!");
    }
}

求可胜操作数，用ans^a[i]得到除a[i]以外的其他值的亦或值，若该值比a[i]小，那么可另a[i]等于该值，使亦或总值等于0.
HDU 1850

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include<stdio.h>
int a[1000002];
int main()
{
    int n;
    while(~scanf("%d",&n),n)
    {
        int ans=0,cnt=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",a+i);
            ans^=a[i];
        }
        if(ans)
        for(int i=0;i<n;i++)
        if((a[i]^ans)<a[i])cnt++;
        printf("%d\n",cnt);
    }
}

hdu 2176(同1850）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include<stdio.h>
int a[200003];
void getans(int n,int res)
{
    for(int i=0;i<n;i++)
        if((a[i]^res)<a[i])printf("%d %d\n",a[i],a[i]^res);
}
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        int res=0;
        for(int i=0;i<n;i++)
            res^=a[i];
        if(res){puts("Yes");getans(n,res);}
        else puts("No");
    }
}

题目2例题 （反向Nim博弈）：
HDU 1907

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        int sum=0;
        int t1=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            int tp;
            scanf("%d",&tp);
            if(tp==1)t1++;
            sum^=tp;
        }
        if(sum==0&&t1!=n||sum!=0&&t1==n)
            puts("Brother");
        else puts("John");
    }
}

hdu 2509

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int tp;
        int sum=0;
        int s1=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&tp);
            sum^=tp;
            if(tp==1)s1++;
        }
        if(sum==0&&s1!=n||sum!=0&&s1==n)puts("No");
        else puts("Yes");
    }
}

S-Nim
sg博弈+nim博弈

证明该解法的正确性：
对于每个队列的sg值k，显然至少从0——k-1的值在后继点中是可以找到的，那么对手选择这0——k-1个后继点，都将导致总亦或值不为0（即Nim博弈的模型），若选择大于k的后继点（如果有的话），当然也是自取灭亡。假如对手选取的点为p（p>k)，那么新产生的所有队列亦或值肯定不为0，只是把修改的队列抬高了而已（对于新的队列，他的后继点至少可以取到1——p-1的所有值）

HDU 1536/1944

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iostream>
#define mem(x,y) memset(x,y,sizeof(x))
#define inf 0x3f3f3f3f
using namespace std;
int a[101],k;
int mmr[10003];
int sg(int n)
{
    if(mmr[n]!=-1)return mmr[n];
    bool vis[101]={0};
    for(int i=0;i<k&&n-a[i]>=0;i++)
        vis[sg(n-a[i])]=1;
    for(int i=0;;i++)
        if(!vis[i])return mmr[n]=i;
}
int main()
{
    while(scanf("%d",&k),k)
    {
        for(int i=0;i<k;i++)
            scanf("%d",a+i);
            sort(a,a+k);
        int t;
        scanf("%d",&t);
        mem(mmr,-1);
        for(int i=0;i<t;i++)
        {
            int n;
            scanf("%d",&n);
            int ans=0;
            for(int i=0;i<n;i++)
              {
                  int l;
                  scanf("%d",&l);
                  ans^=sg(l);
              }
            if(ans)printf("W");
            else printf("L");
            if(i==t-1)puts("");
        }
    }
}

HDU 1848

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iostream>
#define mem(x,y) memset(x,y,sizeof(x))
#define inf 0x3f3f3f3f
using namespace std;
int fb[300];
void gtfb()
{
    int i;
    fb[1]=1,fb[2]=2;
    for(i=3;fb[i-1]<=1000;i++)
        fb[i]=fb[i-1]+fb[i-2];
}
int sg[1004];
int gtsg(int n)
{
    if(sg[n]!=-1)return sg[n];
    bool vis[100]={0};
    for(int i=1;n-fb[i]>=0;i++)
        vis[gtsg(n-fb[i])]=1;
    for(int i=0;;i++)
        if(!vis[i])return sg[n]=i;
}
int main()
{
    gtfb();
    mem(sg,-1);
    sg[0]=0;
    int a[3];
    while(scanf("%d%d%d",&a[0],&a[1],&a[2]),a[0])
    {
        int ans=0;
        for(int i=0;i<3;i++)
            ans^=gtsg(a[i]);
        puts(ans?"Fibo":"Nacci");
    }
}

那么SG博弈是个啥？
对于一个博弈问题，它的下一状态（后继点）只能推到有限个子状态中，那么它就是满足SG博弈的。所以Nim博弈就是一种特殊的SG博弈。
SG值：一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。
后继点：也就是按照题目要求的走法（比如取石子可以取的数量，方法）能够走一步达到的那个点。

sg (X)= min｛n| n∈N ,n≠ for y∈F(x)｝ 就是指x状态下做出决策不能达到的最小状态, sg(x)=0时为必败态.
性质：
（1）对于任意的局面，如果它的SG 值为0，那么它的任何一个后继局面的SG 值不为0；
（2）对于任意的局面，如果它的SG 值不为0，那么它一定有一个后继局面的SG 值为0。

例题 HDU 1847:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iostream>
#define mem(x,y) memset(x,y,sizeof(x))
#define inf 0x3f3f3f3f
using namespace std;
int sg[1003];
int getsg(int n)
{
    if(sg[n]!=-1)return sg[n];
    bool vis[100]={0};
    for(int i=1;i<=n;i*=2)
        vis[getsg(n-i)]=1;
    for(int i=0;;i++)
        if(!vis[i])return sg[n]=i;
}
int main()
{
    int n;
    mem(sg,-1);
    sg[0]=0;
    while(~scanf("%d",&n))
        puts(getsg(n)?"Kiki":"Cici");
}

HDU 1404
用dfs模拟推理过程是一个机智的博弈解决方法。
这个题说明，在不需要加类似Nim博弈的场合，sg值的作用只有两种，0和非0. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 1000002
int sg[maxn];
///sg博弈，给最多6位数字，问胜负情况。
///两种操作：任意位数字减去一个小于它的正整数值；拿走为0的某位以及其后面的所有数。
int dfs(int n)
{
    if(sg[n]!=-1)return sg[n];
    for(int i=1;i<=n;i*=10)
    {
        int t=n;
        if(n/i%10)
        {
            do
            {
                t-=i;
                if(t<i)break;
                ///避免首位减为0的操作
                if(!dfs(t))return sg[n]=1;
            }while(t/i%10);
        }
        else if(!dfs(n/i/10))return sg[n]=1;
        ///如果该位为0，那么拿走该位以及其后的状态是0,则拿走
    }
    return sg[n]=0;
}
int main()
{
    memset(sg,-1,sizeof(sg));
    sg[0]=1;
    for(int i=maxn-1;i>=1;i--)
        dfs(i);
    char s[10];
    int n;
    while(~scanf("%s",s))
    {
        if(s[0]=='0')
            puts("Yes");
        else
        {
            sscanf(s,"%d",&n);
            if(sg[n])puts("Yes");
            else puts("No");
        }
    }
}

拓展：翻硬币游戏，Anti-sg游戏，无向图删边游戏

EOF