Game with a Strip URAL – 2104(DFS+博弈)

题目链接:https://cn.vjudge.net/problem/URAL-2104

题目大意:第1行输入长方形纸条每一面含有的字母数量,第二行输入长方形纸条正面的字母,第三行输入长方形反面的字母,字母只含有A、B两种,分别代表Alice和Bob。博弈游戏开始,Alice先手,Bob后手。对于每个状态,若长方形纸条某一面字母数量为奇数,则认为结束游戏,游戏平局,除此之外,若不能分成胜负(两面全为A则Alice赢、两面全为B则Bob赢),则由场次选手选择折叠方向,使得某一面成为新的正反两面。

解题思路:dfs求得所有情况下的状态(必胜/必败/平),再依据当前是Alice场还是bob场选择最有利于自己的。

Alice场次:

必胜态: A…A|…… 或 ……|A…A
必败态: B…B|B…B
平态: ..A..B..|..A..B..
Bob场次:

必胜态: B…B|…… 或 ……|B…B
必败态: A…A|A…A
平态: ..A..B..|..A..B..
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int dfs(int f,int n,char *a,char *b)
{
    int sum=0;
    if(n%2==1)
    {
        for(int i=0;i<n;i++)
        {
            if(a[i]=='A')
                sum++;
        }
        for(int i=0;i<n;i++)
        {
            if(b[i]=='A')
                sum++;
        }
        if(sum==2*n)return 1;//alice必胜
        else if(sum==0) return -1;//Alice必败
        else return 0;//平
    }
    int l=dfs(f^1,n/2,a,a+n/2);
    int r=dfs(f^1,n/2,b,b+n/2);
    if(f==0)//若为Alice场则要结果尽可能地大才有利于自己
    {
        return max(l,r);
    }
    else return min(l,r);//与Alice相反
}

int main()
{
    ios::sync_with_stdio(false);
    char a[500050],b[500050];
    int n;
    cin>>n;
    cin>>a;
    cin>>b;
    int ans=dfs(0,n,a,b);
    if(ans==1)
    {
        cout<<"Alice"<<endl;
    }
    else if(ans==0)
    {
        cout<<"Draw"<<endl;
    }
    else cout<<"Bob"<<endl;
    return 0;
}

———————
题目大意部分及部分解题思路参考自:https://blog.csdn.net/BlessingXRY/article/details/79178461

发表评论

电子邮件地址不会被公开。 必填项已用*标注