题目概述

CF1527B

解题报告

我来翻译题解啦！

由于不是回文串的时候才能进行操作2，所以我们可以认为操作2是执行一次“啥都不干”。

如果 $s$ 是回文串（B1）：

• 如果 $n$ 是偶数：Bob必胜，因为只要Alice将一个 $0$ 改成 $1$ ，Bob就把对位的 $0$ 改成 $1$ 。到最后一组 $0$ 的时候，Bob使用操作2，这样就肯定比Alice少花费 $2$ 元。

• 如果 $n$ 是奇数：

  • 如果最中间是 $0$ ，并且还有其他 $0$ ：Alice胜利，因为Alice可以通过把中间的 $0$ 改成 $1$ ，把局势变为 $n$ 为偶数的情况，这样Bob就会比Alice多花费 $1$ 元。
  • 否则还是Bob胜利。

如果 $s$ 不是回文串（B2）：

• 如果 $n$ 是奇数，并且只有两个 $0$ ，并且中间是 $0$ ：显然平局。
• 否则Alice必胜，因为Alice可以不停的使用操作2，直到剩下最后一个不对称的 $01$ ，将 $0$ 改成 $1$ 。这样就把局势转化为 $n$ 为偶数的回文串情况。Alice至少比Bob少花费 $1$ 元。

示例程序

#include<cstdio>
using namespace std;
const int maxn=1000;

int te,n,cnt;char s[maxn+5];bool fl;

int main(){
    for (scanf("%d",&te);te;te--){
        scanf("%d%s",&n,s+1);fl=true;
        for (int i=1;i<=n;i++) if (s[i]!=s[n-i+1]) fl=false;
        if (fl){
            cnt=0;for (int i=1;i<=(n>>1);i++) cnt+=(s[i]=='0');
            if ((n&1) && s[n+1>>1]=='0') puts(cnt?"ALICE":"BOB");
            else puts("BOB");
        } else {
            cnt=0;for (int i=1;i<=n;i++) cnt+=(s[i]=='0');
            puts((n&1) && cnt==2 && s[n+1>>1]=='0'?"DRAW":"ALICE");
        }
    }
    return 0;
}