题目链接

题目大意

给你一个01串，先后手依次进行操作。操作有两种：

1. 将序列中的一个0改成1，并付出1点代价。
2. 翻转序列（当序列不为回文串时），并付出0点代价。翻转序列的前一步不能是翻转序列。

现在Alice先手进行操作，Bob后手进行操作。当整个序列变成全1串时，游戏结束。求解游戏结束时，两者中代价较小的一方。

输出先手胜/后手胜/平局。

解题思路

本题有一个前置的easy版本的题目（参考cf链接中的b1）即给出的01串必定是回文串。

我们先考虑简单版本下的解决方法：

1. 当给出全1串时，平局。
2. 当给出给出的串只有一个0时，后手胜。
3. 当给出的串长是偶数，后手胜。
4. 当给出的串长是奇数且中间为1时，后手胜。
5. 当给出的串长是奇数且中间为0时，先手胜。

下面给出上述结论的简易证明。

1. 显然
2. 若只有一个0，必定在串长为奇数的中间（因为回文串限制）。此时先手只能更改其为1，后手胜。
3. 以1001举例，先手只能修改，变为1101；此时后手可以翻转，而先手被迫再次修改1111。游戏结束，先手2分后手0分，后手胜。（复杂情况同理，不再赘述）
4. 此时中间的1可以抹除。等同于偶数情况，后手胜。
5. 先手改动中间的0为1，此时相当于4.中的情况，只是转变了先后手，原先的先手必胜。

未完待续。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6+7;
int T;
int n,m,k;
char a[N];

signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        cin>>a;
        int cnt=0;
        for(int i=0;i<n;i++){
            if(a[i]=='0'){
                cnt++;
            }
        }
        //cout<<cnt<<endl;
        if(cnt==0){
            cout<<"DRAW\n";
        }
        else if(cnt==1 || n%2==0){
            cout<<"BOB\n";
        }
        else if(n%2==1 && a[(n-1)/2]=='0'){
            cout<<"ALICE\n";
        }
        else{
            cout<<"BOB\n";
        }
    }
    return 0;
}