博弈论浅析-练习题浅解

本文中的练习题是这篇帖子下的练习题,如果不太了解博弈论,建议先阅读这篇帖子:
博弈论浅析 - #2

如果你希望亲自完成这些题目请务必不要提前阅读题解,否则只会给你“这些题很简单”的错觉。
当然,对于大佬来说就是很简单就是了

NC15826 chess

题意:
棋盘上有一个皇后,游戏双方每次可以选择向左移动、向下移动和向左下方向移动,且可以移动任意多步,不能移出边界,谁先移动到棋盘左下角谁赢。给出皇后坐标,问先后手谁必胜。
浅解:
可以将皇后的 x,y 坐标看成两堆石子,那题意方向移动就是取石子操作。而这种取石子规则就是威佐夫博弈。按照威佐夫博弈的模板就可解答。(有可能因为精度问题导致要把公式换种方法来进行条件判断。虽然我对拍了很久还是没找到哪个数据会导致精度问题…)

Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
    /*
    for(int i=1;i<10000;i++)
    {
        isin[(int)(((sqrt(5)+1)/2)*i)]=1;
        whati[(int)(((sqrt(5)+1)/2)*i)]=i;
    }
    */
    int a,b;
    while(cin>>a>>b)
    {
        if(a>b)swap(a,b);

        //if(isin[a]&&b==a+whati[a])
        if(((int)((b-a)*((sqrt(5)+1)/2)))==a)//用这种方式才行,前面可能因为精度问题答案错误
        {
            cout<<"Lao Wang"<<endl;
        }
        else
        {
            cout<<"Xiao Ren"<<endl;
        }
    }
    return 0;
}

POJ2311

题意:
给一个有 W*H 网格的纸,双方每次可以进行一个操作,选择一个纸,将其沿着网格线剪成两部分,可以选择竖直方向剪纸或水平方向剪纸,如一个 6*8 大小的纸可以剪成两个纸,分别是 2*84*8 。谁将剪到 1*1 的纸谁就赢,问先后手谁必胜。
浅解:
首先发现,这个游戏是不是寻常的SG游戏,因为它不满足“谁无法行动谁就输了“这个规则。但是我们可以稍加修饰。因为如果谁先剪到了 1*x ,那另一方一定会在下个回合将 1*x 剪成 1*11*x-1 ,所以双方除非到没有其他行动的地步,否则都不会剪到 1*x 。那么我们就不妨将胜负规则转变为“谁都不能剪到 1*x 形状的纸,谁不能行动谁就输”,这样就变回我们熟悉的SG游戏了。
再看看剪纸操作是将一个纸变成两个纸,是典型的Muti-SG游戏,再用Multi-SG游戏的方法就能解出答案。

Code
#include<iostream>
#include<set>
#include<string.h>
#include<iterator>
using namespace std;
typedef long long ll;
ll dp[205][205];
int dfs(int w,int h)
{
    if(w>h)swap(w,h);
    if(dp[w][h]!=-1)return dp[w][h];
    if(w==2&&h==2){
        dp[w][h]=0;
        return 0;
    }
    set<int>se;
    for(int i=2;i<=w-2;i++)
    {
        int t=dfs(i,h)^dfs(w-i,h);
        se.insert(t);
    }
    for(int i=2;i<=h-2;i++)
    {
        int t=dfs(w,i)^dfs(w,h-i);
        se.insert(t);
    }
    int cnt=0;
    for(set<int>::iterator it=se.begin();it!=se.end();it++)
    {
        if(*it!=cnt)
        {
            break;
        }
        else
        {
            cnt++;
        }
    }
    dp[w][h]=cnt;
    return cnt;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h,w;
    memset(dp,-1,sizeof(dp));
    while(cin>>w>>h)
    {
        if(w<2&&h<2)
        {
            cout<<"WIN"<<endl;
            continue;
        }
        if(w>h)swap(w,h);
        if(dfs(w,h)!=0)cout<<"WIN"<<endl;
        else cout<<"LOSE"<<endl;
    }

    return 0;
}

CEOI2008 Knights

题意:
n*n 大小的棋盘上有 k 个骑士,这 k 个骑士可以按照国际象棋骑士的行动规则走,但只能走向左的两个方向和向下的两个方向。双方轮流操作,每次操作必须把所有能行动的骑士都行动一次,骑士位置可以重合。当一方没有能行动的骑士时,该方输,问先后手哪方必胜。且如果先手必胜,给出第一轮每个骑士的一个必胜走法,数据保证每个骑士至少能走一次。
浅解:
每个可以行动的骑士都要行动一次,这是典型的Every-SG游戏了,这类游戏我们要通过单个游戏的SG值找到step值,最后根据step值来求正解。但对于单个游戏的行动,好像分析不出什么规律,这种时候就只能打表了(这个表的左上角相当于棋盘的左下角):

这是n=30时打表出来的step 值,还是能找出规律的。但是要注意边界地方的规律会发生变化,且还和n的值有关。这就要慢慢找规律了。最后找规律后得出的代码如下:

Code
#include<bits/stdc++.h>
using namespace std;
int n;
int knight[200005][3];
int checkstep(int x,int y)
{
    x--;y--;
    if(n%4==0&&(x==n-1||y==n-1))
    {
        if(y>x)swap(x,y);
        if(x==n-1&&y==n-1)
            return checkstep(x-1,y-1)+2;
        else return checkstep(x,y+1);

    }
    if(n%4==1&&(x==n-1||y==n-1)&&n!=1)
    {
        if(y>x)swap(x,y);
        if(x==n-1&&y==n-2)
            return checkstep(y+1,y+1);
        else
            return ((x/4)+(y/4))*2;
    }
    if(x%4<2&&y%4<2)
    {
        return ((x/4)+(y/4))*2;
    }
    else
    {
        return ((x+y-1)/4)*2+1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
cin.tie(0);
    int k;
    cin>>k>>n;
    int maxstep=0;
    for(int i=0;i<k;i++)
    {
        cin>>knight[i][1]>>knight[i][2];
        knight[i][0]=checkstep(knight[i][1],knight[i][2]);
        if(knight[i][0]>maxstep)maxstep=knight[i][0];
    }
    if(maxstep%2==0)
    {
        cout<<"NO";
        return 0;
    }
    cout<<"YES"<<endl;
    for(int i=0;i<k;i++)
    {
        int x=knight[i][1];
        int y=knight[i][2];
        for(int j=0;j<4;j++)
        {
            int xx=x+dx[j];
            int yy=y+dy[j];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=n)
            {
                if(checkstep(xx,yy)==knight[i][0]-1)
                {
                    cout<<xx<<' '<<yy<<endl;
                    break;
                }
            }
        }
    }
}

此外,对于先手必胜情况的每个骑士的行动,选择能踏入下一个step的位置即可。因为求step值的过程,就是先后手轮流取最优解的过程。

CF305E Playing with String

题意:
初始给一个字符串,双方轮流行动,每次行动找到一个字符串中的一个长度大于 1 且为奇数的回文子串,然后以回文子串的中心字符为基准,将这个字符串分成三份。无法行动者输,问先后手谁胜谁负。如果是先手必胜,再求先手的第一次必胜行动,可以选择的位置最小的分割点。
浅解:
可以发现每次分割,只要两个回文中心不是相邻的,那么分割哪一个先都不会对另一个产生影响。所以可以把不相邻的回文中心看成是不同的SG游戏。再看单个SG游戏,即假设有一个长度为 n 的连续回文中心,那么当分割其中的第 i 位时,其中第 i-1 , i+1 位的字符就构成不了回文中心了,那接下来就剩下一个长度为 i-2 的连续回文中心和一个长度为 n-i-1 的连续回文中心。这样看就是典型的Multi-SG游戏的规则了。
就这样求出谁胜谁负后,如果是先手必胜,再求出哪个操作执行后能够使游戏的总SG值为 0 ,那这个操作对应的回文中心就是合法的分割点。求位置最小的话,那判断合法性的时候从小的那端开始就行了。

Code
#include<bits/stdc++.h>
using namespace std;
int sg[5005];

void init()
{
    sg[0]=0;
    for(int i=1;i<=5000;i++)
    {
        bool mex[5005]={0};
        for(int j=1;j<=i;j++)
        {
            int xo=sg[max(0,j-2)]^sg[max(0,i-j-1)];
            mex[xo]=1;
        }
        for(int j=0;j<=5000;j++)
        {
            if(mex[j]==0)
            {
                sg[i]=j;
                break;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    string str;
    cin>>str;
    int len=str.length();
    int xo=0;
    for(int i=1;i<len-1;i++)
    {
        if(str[i-1]==str[i+1])
        {
            int j=i;
            while(j+2<len&&str[j]==str[j+2])j++;
            xo^=sg[j-i+1];
            i=j;
        }
    }
    if(xo==0)
    {
        cout<<"Second";
        return 0;
    }
    else
    {
        cout<<"First"<<endl;
        for(int i=1; i<len-1; i++)
        {
            if(str[i-1]==str[i+1])
            {
                int j=i;
                while(j+2<len&&str[j]==str[j+2])
                {
                    j++;
                }
                xo^=sg[j-i+1];
                for(int k=i;k<=j;k++)
                {
                    if((xo^sg[max(0,k-i-1)]^sg[max(0,j-k-1)])==0)
                    {
                        cout<<k+1;
                        return 0;
                    }
                }
                xo^=sg[j-i+1];
                i=j;
            }
        }
    }

}

Luogu3235 HNOI2014 江南乐

题意:
n 堆石子,双方轮流行动,每次可以选择数量不小于 f 的一堆石子,然后尽量将其均分为 m 等份, m 的值由游戏方自行决定。不能行动者输,求先后手谁胜谁负。
浅解:
和“博弈论浅析”中分析过的“Lunch”这道题类似,在分的石子堆中,只需要注意奇数堆的SG值即可。
在分堆循环中,分的堆数并不是一个个加,而是对于分出来的石子数量重复时,就不会考虑这种情况,即可以跳着考虑,这样就不会是平方级的时间复杂度了。具体实现看代码。

Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int sg[100005]={0};
int mex[100005]={0};

int f;

int dfs(int v)
{
    if(v<f)return 0;
    if(sg[v]!=0)return sg[v];

    for(int i=2;i<=v;i=v/(v/i)+1)//i是分的堆数
    {
        int t=0;
        if((v%i)%2==1)t^=dfs(v/i+1);
        if((i-v%i)%2==1)t^=dfs(v/i);
        mex[t]=v;
        if(i+1<=v)
        {
            int j=i+1;
            int t=0;
            if((v%j)%2==1)t^=dfs(v/j+1);
            if((j-v%j)%2==1)t^=dfs(v/j);
            mex[t]=v;
        }
    }
    for(int i=0;i<=100000;i++)
    {
        if(mex[i]!=v)
        {
            sg[v]=i;
            break;
        }
    }
    return sg[v];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t>>f;
    for(int i=0;i<t;i++)
    {
        int a,b;
        cin>>a;
        int xo=0;
        for(int j=0;j<a;j++)
        {
            cin>>b;
            xo^=dfs(b);
        }
        if(xo==0)cout<<"0"<<' ';
        else cout<<"1"<<' ';
    }
    return 0;
}
粤 ICP 备 2020080455 号