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