博弈论题目

Eric20521 · 2020-03-20 17:23:33 · 个人记录

一、【P1290 欧几里德的游戏】

https://www.luogu.com.cn/problem/P1290

对于数对 ( a , b ) , 不妨规定 a < b

首先确定终局条件 : a == 0

然后考虑面对 （ a , b ) 时，本质上只有两种选择：

1.得到 （ a , b%a )

2.得到 （ a , b%a + b )

而 2 定会去到 1 ，所以两种局面胜负性相反。

故当两种都可到达，则必胜；否则只能到 1 则需要 1 为必败才可取胜，反之亦然。

#include<iostream>

using namespace std;
int t;
int a,b;

bool dfs(int a,int b){
    if(a>b) swap(a,b);
    if(a==0) return 0;
    if(b/a==1) return 1^dfs(a,b%a);
    else return 1;
}

int main(){
    cin>>t; 
    while(t--){
        cin>>a>>b;
        if(a>b) swap(a,b);
        if(dfs(a,b)) cout<<"Stan wins\n";
        else cout<<"Ollie wins\n";
    }   
    return 0;
} 

二、【P1288 取数游戏II】

https://www.luogu.com.cn/problem/P1288

发现移动时直接变为 0 即可，否则对方原路返回并变为 0 只会再回到原来局面的基础上变得更糟（一边为 0 ，没有了选择 ）

故游戏过程为从起点出发，向左/右一直移动，碰到 0 为止

所以检查起点距离 0 边距离的奇偶性，两条路只要存在奇数长度（参考 1 ）便必胜，否则必败

#include<iostream>
#define maxn 20

using namespace std;
int n;
int a[maxn];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int cntl=0,cntr=0;
    for(int j=1;j<=n;j++){
        if(a[j]==0) break;
        cntr++;
    }
    for(int j=n;j>=1;j--){
        if(a[j]==0) break;
        cntl++;
    }

    if(cntl%2==1 || cntr%2==1) cout<<"YES\n";
    else cout<<"NO\n";

    return 0;
}

三、【CF917B MADMAX】

https://www.luogu.com.cn/problem/CF917B

描述一个局面需要双方所在位置以及目前的字母限制，这样 n ^ 2 * 26 的局面数可以直接dfs解决。

#include<iostream>
#include<vector>
#include<cstring>
#define maxn 105
using namespace std;
int n,m;
struct edge{
    int v;
    char w;
    edge(int v=0,int w=0):v(v),w(w){}
};
vector<edge> e[maxn];

int sg[maxn][maxn][30];
bool dfs(int i,int j,int rs){
    //cout<<i<<" "<<j<<" "<<rs<<endl;

    if(sg[i][j][rs]!=-1) return sg[i][j][rs];
    int v,r;
    for(int k=0;k<e[i].size();k++){
        v=e[i][k].v;
        r=e[i][k].w;
        if(r<rs) continue;
        if(dfs(j,v,r)==0) return sg[i][j][rs]=1;
    }
    return sg[i][j][rs]=0;
}

int main(){
    cin>>n>>m;
    int u,v;
    char c;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>c;
        e[u].push_back(edge(v,c-'a'));
    }

    memset(sg,-1,sizeof(sg));

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dfs(i,j,0)==1) cout<<"A";
            else cout<<"B"; 
        }
        cout<<endl;
    }

    return 0;
} 

四、【P2575 高手过招】

https://www.luogu.com.cn/problem/P2575

可将每一行单独考虑，状压的方式计算每个局面的 sg 值，将每行对应的异或起来即可，理论的直接应用。。。

使用记忆化搜索，每种局面去到的下一个局面也是固定的

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;
int t;
int n;
int m;

int sg[(1<<21)];
int dfs(int x){
    if(sg[x]!=-1) return sg[x];

    bool vis[30];
    memset(vis,0,sizeof(vis));

    int lst0=-1;
    for(int j=20;j>=1;j--){
        if((x&(1<<j))==0) {
            lst0=j;
            continue;
        }
        else {
            if(lst0==-1) continue;
            vis[dfs(x^(1<<j)^(1<<lst0))]=1;
        }
    }
    for(int i=0;i<20;i++){
        if(!vis[i]) return sg[x]=i;
    }
}

int main(){
    cin>>t;
    memset(sg,-1,sizeof(sg));
    while(t--){
        cin>>n;
        int ans=0;
        for(int i=1;i<=n;i++){
            int k,x=0;
            cin>>k;
            while(k--){
                int j;
                cin>>j;
                x|=(1<<j);
            }
            ans^=dfs(x);
        }
        if(ans==0) cout<<"NO\n";
        else cout<<"YES\n";
    }
    return 0;
} 

五、【Acwing 219. 剪纸游戏】

https://www.acwing.com/problem/content/221/

每一个最基础的局面通过 （ x , y ) 来表示，即一张 x * y 的纸。

依然是 dfs 求 sg 值。对于一次剪出来的两片 （x1 , y1 ) 与 (x2 , y2 ) 应通过 或 的方式合并；一张纸不同的剪法，通过 mex 来合并。

#include<iostream>
#include<cstring>

using namespace std;
int n,m;
int sg[205][205];
int dfs(int x,int y){
    if(sg[x][y]!=-1) return sg[x][y];
    if(sg[y][x]!=-1) return sg[x][y]=sg[y][x];

    if(x==1 && y==1) return sg[x][y]=0;

    bool vis[400];
    memset(vis,0,sizeof(vis));
    for(int i=2;i<x-1;i++){
        vis[dfs(i,y)^dfs(x-i,y)]=1;
    }
    for(int j=2;j<y-1;j++){
        vis[dfs(x,j)^dfs(x,y-j)]=1;
    }

    for(int i=0;i<400;i++){
        if(vis[i]==0) return sg[x][y]=i;
    }
}

int main(){
    memset(sg,-1,sizeof(sg));
    while(cin>>n>>m){
        if(dfs(n,m)!=0) cout<<"WIN\n";
        else cout<<"LOSE\n";
    }

    return 0;
}

六、【AcWing 235. 魔法珠】

https://www.acwing.com/problem/content/description/237/

与上一题 剪纸游戏 基本一致，这里剪开两张纸对应分裂，不同剪法对应选择不同的进行分裂，终局为全 1 必败。

同样通过 dfs 合并 sg 值来实现

#include<iostream>
#include<cstring>
#define maxn 105
#define maxa 1005

using namespace std;
int n;

int sg[maxa];
int dfs(int x){
    if(x==1) return sg[x]=0;

    int d[40];
    int top=0;
    d[++top]=1;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            d[++top]=i;
            if(i*i!=x) d[++top]=x/i;
        }
    }

    int ans=0;
    for(int i=1;i<=top;i++){
        ans^=dfs(d[i]);
    }
    bool vis[40];
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=top;i++){
        vis[ans^dfs(d[i])]=1;
    }

    for(int i=0;i<40;i++){
        if(vis[i]==0) return sg[x]=i;
    }
}

int main(){
    while(cin>>n){
        int ans=0;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
           ans^=dfs(x);
        }

        if(ans==0) cout<<"rainbow\n";
        else cout<<"freda\n";
    }
    return 0;
}

七、【P1199 三国游戏】

https://www.luogu.com.cn/problem/P1199

将组合按照默契值排序之后，对于这个有序排列：

任意一个武将第一次出现的组合一定拿不到（当拿到其中一个后，立刻被抢走另一个……），而也正因为这样，第二次出现定能拿到，所以所有武将中第二次出现的最靠前的即是答案。

而考虑胜负，在为第二次出现做铺垫，选取第一次出现的组合时，电脑拿到的定也是第一次出现（因为你选择的是第二次出现最早的），所以不用担心电脑拿到第一次出现的组合。（大概是这样，需要想一想）

#include<iostream>
#define maxn 505
#include<algorithm>

using namespace std;
int n;
bool app[maxn];
struct partner{
    int x,y,w;
    partner(int x=0,int y=0,int w=0):x(x),y(y),w(w){}
    bool operator < (const partner &t)const{
        return w>t.w;
    }
};
partner a[maxn*maxn]; 
int top=0;

int main(){
    cin>>n;
    int w;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>w;
            a[++top]=partner(i,j,w);
        }
    }

    sort(a+1,a+1+top);

    for(int i=1;i<=top;i++){
        if(app[ a[i].x ] || app[ a[i].y ]) {
            cout<<1<<"\n"<<a[i].w;
            return 0;
        }
        app[ a[i].x ] = app[ a[i].y ] = 1;
    }

    return 0;
}

八、【AcWing 236. 格鲁吉亚和鲍勃】

https://www.acwing.com/problem/content/238/

通过神奇的转化：将石子按顺序两两配对，只需考虑每对之间的距离（因为每对可以通过两人的操作同时左移），转化为一个nim游戏的局面（n堆石子，每次从一堆取，取完为止），which 有一个特性，可通过每个值直接异或起来是否为零来判断先手胜负。

注意输入并不有序 > _ <

#include<iostream>
#define maxn 1005
#include<algorithm>

using namespace std;
int t;
int n;
int a[maxn];

int main(){
    cin>>t;    
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        if(n%2==1) a[++n]=0;
        sort(a+1,a+1+n);
        int ans=0;
        for(int i=2;i<=n;i+=2){
            ans^=a[i]-a[i-1]-1;
        }
        if(ans) cout<<"Georgia will win\n";
        else cout<<"Bob will win\n";
    }
    return 0;
}