Lut本科回忆录

这场我真的会谢，A题都看错意思了快20min才开出来
c做到一半以为不会就玩手机去了，结束后仔细做会儿改个bug就出来了
so，补个D吧

题目给t(1<=t<=1000)个操作，每个操作输入一个源字符串(长度为偶，且len<=2000)，同时Alice和Bob各有一个字符串且初始都为空，即""。
每次操作每个人可以从源字符串的头或尾选择一个字符剪切到自己字符串的头部。
当源字符串为空时，两个人的字符串按字典序比较，小的人获胜。
问是Alice或BOb胜还是平局。

字符区间为[l,r]时，每一轮二人都可选择一个字符,显然有以下选择

Alice Bob
s[l]  s[l+1]
s[l]  s[r]
s[r]  s[l]
s[r]  s[r-1]

对于一轮操作中的两个字符，要么s[i]==s[j],要么s[i]!=[j]，可知Alice先手，则先手必然选择最优结果
以此类推当两个字符不同时，Alice是必胜状态，此外Bob不存在胜利情况。

我们可以用一个二维dp[i][j] 表示下标 i 到 j 之间Alice是否处于必胜状态，否则就是平局

由题目数据可知我们要查询区每段区间，有（n*n）/2 的复杂度，因为数据量比较小，还是可以过的

int dp[3000][3000];
int dfs(int l,int r){
    //已经查询过了
    if(dp[l][r]!=-1)return dp[l][r];
    //仅剩最后两个字符，不相等则Alice必胜，反之平局
    if(l+1==r)return s[l]!=s[r];
    int flag=0;
    //查询四种情况，要么选择的使得Alice必胜，要么剩下的字符串使得Alice必胜

    //当Alice选择s[l]时，不论Bob选择s[l+1]ors[r]都赢
    if((dfs(l+2,r)||s[l]<s[l+1])&&(dfs(l+1,r-1)||s[l]<s[r]))flag=1;
    //当Alice选择s[r]时，不论Bob选择s[r-1]ors[l]都赢
    if((dfs(l,r-2)||s[r]<s[r-1])&&(dfs(l+1,r-1)||s[r]<s[l]))flag=1;
    return dp[l][r] = flag;
}
void solve()
{
    cin>>s;
    int len=s.size();s=' '+s;
    //初始化
    rep(i,1,len){
        rep(j,1,len){
            dp[i][j]=-1;
        }
    }
    if(dfs(1,len))cout<<"Alice"<<endl;
    else cout<<"Draw"<<endl;
}

害。