@1.Palindrome Game (easy version)

题目

题意:回文串游戏.给出一个由0和1组成的回文串(至少有一个0).alice先手,bob与alice一人一回合.每一回合操作

1.选字符串中的一个0把它变成1,消耗1精力;

2.若字符串本身不是回文串,且上一回合进行的是1操作,那么将这个字符串反转,不耗费精力

当字符串全是1时游戏结束

Alice和BOB都用最优策略,问最终谁耗费的精力最少,或者一样多(平局是迷惑人的)?

策略:

如果要操作1,优先让操作完后的字符串变成回文串,这样可以让下一回合的人不能使用交换,不然的话,下一个人交换,然后再下一回合你又不能用交换,又多消耗一点精力,这样铁定不是最优的策略,相当于白白消耗了自己2点精力

每一个严格的对可以由 a+1 b a+1(或a+1 b+1)消灭 然后ab交换身份 谁当上第一个要选的(因为刚开始是回文串,所以只能操作1),那么后面那个人一定可以灵活操作,最终让第一个人多两次操作

分类讨论即可:

1.如果全是严格的对:alice第一个要选,BOB胜

2.如果有一个非严格的对:A刚开始就选择填上这个空a+1,BOB第一个要选,从此b-a=2;最终b-a=1;ALICE胜

最终别忘了特判只有1个'0'的情况,由于ALICE先手,操作完后就不存在BOB操作了,所以BOB胜利

#include<iostream>
using namespace std;
char s[1004];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n>>s;
        int cnt=0;
        for(int i=0;i<n;++i) {if((s[i]&15)==0) {++cnt;}}
        if(cnt==1) {cout<<"BOB\n";continue;}
        cnt>>=1;
        if(n%2==0||(s[n>>1]&15)) {cout<<"BOB\n";}
        else {cout<<"ALICE\n";}
    }
    return 0;
}