CF1728D题解

Deft_t · 2022-09-09 15:57:21 · 题解

思路

本题的博弈可以先找到必胜局面。 以长度为 3 举例，发现 \texttt{aba bab abc acb aaa baa aab abb} 这些情况都是后取必胜。可以继续推断出长度为奇数的时候都是后取者必胜。
长度为偶数时，除了平局的情况，先取者可以直接构造出后取必胜局面。
题目当中只存在长度为偶数的情况，因此只需要考虑什么时候可以平局。因为此时后取者 Bob 最多只能平局，所以只能在他之前的 Alice 取什么，他就取什么。要注意的是，初始的时候存在头尾相同的时候可以一直头尾跟随互相拿。在这之后就只能相邻相同的才可以拿到相同的。例如 \texttt{aabccb} 这种情况是不能平局的（先取者只需要先取 \texttt{b} 后取者就无法跟随）。
综上，此题就可以解决了。

代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
int p[2005],cnt;
int main()
{
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int len = s.length();
        if(len%2==0){
            bool ok = true;
            int i = 0,j = len-1;
            while(i<j&&s[i]==s[j]){
                i++,j--;
            }
            for(;i<j;i+=2){
                if(s[i]!=s[i+1]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                cout<<"Draw"<<endl;
                continue;
            }
        }
        if(len&1) cout<<"Bob"<<endl;
        else cout<<"Alice"<<endl;
    }
    return 0;
}