• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

专题1 – 博弈

开发技术 开发技术 3小时前 2次浏览

朱朱还是博不起来!

打算缕缕到现在遇到过的博弈问题,虽然XCPC其实不怎么遇到,但是还是得防他一手。

首先,提一下博弈的类型。

以下提到的所有博弈都是ICG游戏的博弈,ICG游戏的条件如下:

1、有且仅有两人。

2、两人交替进行合法的移动。

3、合法的移动集合仅取决于局面本身。

4、无法进行合法移动即判负。

所以,日常情况下,大多数的游戏并非ICG。(比如象棋、围棋,就连五子棋也不是)

一、巴什博弈

题目的表述通常都可以转述成:一共有(n)个物品,每次最少取(1)个,最多取(m)个,取完者胜(或者负),问谁能获胜。

那这里就仅仅讨论取完者胜的情况,结论就是仅当(n%(1+m)=0)时先手必败,其余情况先手必胜。原因很简单,先手可以把余数部分取掉,而后凑(1+m)即可。

例题:HDU – 1846

完完全全的模板题,写就完了。

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
int main()
{
    fast;
    int c;
    cin >> c;
    while (c--)
    {
        int n, m;
        cin >> n >> m;
        if (n % (1 + m) == 0)
            cout << "secondn";
        else
            cout << "firstn";
    }
}

当然,巴什博弈也有一定的拓展,有时取的下限并非(1),将每次取值的范围控制在(p)和(q)之间。

例题:HDU – 2897

我们可以通过同样的方法计算(n%(p+q))的值,当这个值为大于(0)且小于等于(p)时,无论先手取何值(k),后手只需要取对应的(p+q-k),这样维持原博弈状态,直至只剩下这个余数,先手必败。余数大于(p)时,我只需要取使得剩下部分的余数小于(p)即可,这样对方处在必败态。等于(0)时,取最大值,后手要么维持余数为(0),这种情况下先手胜;要么取(k),而先手对应取(p+q-k)即可,这样最后一部分只能留给后手取。

最终得出结论:余数大于(0)小于等于(p)先手败,否则先手胜。

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
int main()
{
    fast;
    int n, p, q;
    while (cin >> n >> p >> q)
    {
        if (n % (p + q) > 0 && n % (p + q) <= p)
            cout << "LOSTn";
        else
            cout << "WINn";
    }
}

二、斐波那契博弈

一个结论性的博弈罢了。

有(n)个物品,两人轮流取,第一次可以取任意个(但不能取完),之后的每一次取的个数不超过上一次的(2)倍,问胜负情况。

涉及到一个名字叫做“k倍动态减法游戏”(一篇初中生写的论文)。当(k=2)时,仅当(n)为斐波那契数时必败,其余情况必胜。具体的证明过程我还得看看。

例题:HDU – 2516

#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;
ll fi[3000];
int main()
{
    fast;
    int n;
    ll temp=pow(2,31);
    fi[1]=1;
    fi[2]=2;
    int m;
    for(int i=3;;i++)
    {
        fi[i]=fi[i-1]+fi[i-2];
        if(fi[i]>=temp)
        {
            m=i;
            break;
        }
    }
    while(cin>>n)
    {
        int flag=1;
        if(n==0) break;
        for(int i=1;i<=m;i++)
        {
            if(fi[i]==n)
            {
                flag=0;
                break;
            }
            if(fi[i]>n) break;
        }
        if(flag) cout<<"First winn";
        else cout<<"Second winn";
    }
    return 0;
}

三、威佐夫博弈

初次接触是和孙爹打某场牛客遇到的一道题E-Seek the Joker II_第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛(同步赛) (nowcoder.com)

当时直接采取了一个打表进行一个暴力然后过了,赛后查了一下居然是一种我从未知晓的博弈类型。

有两堆个若干个物品,两个人轮流从任一堆取至少一个或同时从两堆中取相同数量的物品,取完者胜。(改自百度百科)

不证明,直接给结论:假设小堆个数为(a),大堆个数为(b),如果(a=(int)((b-a)*(sqrt(5)+1)/2)),那么先手必败,否则先手必胜。

例题:HDU – 1527

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
int main()
{
    fast;
    int a, b, num;
    double k = (sqrt(5.0) + 1) / 2;
    while (cin >> a >> b)
    {
        if (a > b)
        {
            int temp;
            temp = a;
            a = b;
            b = temp;
        }
        num = b - a;
        if (a == (int)(num * k))
            cout << "0n";
        else
        {
            cout << "1n";
        }
    }
    return 0;
}

四、NIM博弈

NIM博弈的模型是:给(n)堆石子,两人轮流从某一堆石子中取走一定数量的石子(可取完,但不能不取),取完者胜。

这边先引出两个概念:(P-position)和(N-position),前者可以理解为先手必败的状态,后者理解为先手必胜的状态。

引申出如下三条性质:

1、无法进行移动的状态都是(P-position)。

2、能移动到(P-position)的状态是(N-position)。

3、所有移动都导致(N-position)的状态是(P-position)。

以上可作为博弈的总体思路,在比赛中对陌生的博弈进行分析。

那么这边提到的NIM博弈证明呢,懒得找了,所以直接给出一个非常简单的结论。

所有数字异或结果为(0)先手必败,否则先手必胜。

就这么简单,我不懂,但我大为震撼。

例题:HDU – 2176

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
int main()
{
    fast;
    int n;
    int a[200010];
    while(cin>>n)
    {
        if(n==0) break;
        int ans=0;
        int x;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            ans^=a[i];
        }
        if(ans==0) cout<<"Non";
        else
        {
            cout<<"Yesn";
            for(int i=1;i<=n;i++)
            {
                int s=ans^a[i];
                if(s<a[i]) cout<<a[i]<<' '<<s<<'n';
            }
        }
        
    }
    return 0;
}

当然,还没结束。假设对每堆的取法做出限制,该如何解决。

这边需要引入SG函数

我们可以把所有状态的转移抽象成一张有向无环图,每一条边相当于状态的转换。

这边先引出一个函数(mex),表示最小不属于某个集合的非负整数。比如(mex{0,2,3}=1),(mex{1,2,3}=0)。

对于任意一点,其SG值等于其所有后继SG值的(mex)。并且根据上文提到的性质,可以类推出:

1、SG值为0时的状态为(P-position)。

2、SG值为0时,其后继的所有状态都是(N-position)。

3、SG值不为0时的状态为(N-position),必定存在后继的SG值为0。

那么对于某一个堆,我们就可以看作是一个对应SG值个数的取石子游戏,然后按照NIM博弈的异或操作进行处理即可。

例题:HDU – 1848

#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int f[3010];
int sg[3010]={0};
void get_sg(int n)
{
    for(int i=1;i<=n;i++)
    {
        int vis[3010]={0};
        for(int j=1;f[j]<=i;j++)
        {
            vis[sg[i-f[j]]]=1;
        }
        for(int j=0;j<=1000;j++)
        {
            if(!vis[j])
            {
                sg[i]=j;
                break;
            }
        }
    }
}
int main()
{
    fast;
    f[1]=1;
    f[2]=2;
    for(int i=3;;i++)
    {
        f[i]=f[i-1]+f[i-2];
        if(f[i]>1000) break;
    }
    get_sg(1000);
    int n,m,p;
    while(cin>>n>>m>>p)
    {
        if(n==0 && m==0 && p==0) break;
        if(sg[n]^sg[m]^sg[p])
        {
            cout<<"Fibon";
        }
        else cout<<"Naccin";
    }
    return 0;
}

另外,打表的代价非常大,如果数据范围太大,则需要通过小范围打表,找到更明显的规律进行求解。

以上,就是比较常见且基础的博弈类型与做法。那么对于一般的博弈,首先是看能否用以上的方法进行处理。如果无法处理,则可以通过DFS打表找规律,然后归纳出博弈的结果。


程序员灯塔
转载请注明原文链接:专题1 – 博弈
喜欢 (0)