Codeforces Round ＃721 (Div. 2)B1. Palindrome Game (easy version)B2. Palindrome game (hard version)

Look who is playing this autistic div.
Oh , It turned out to be me .
C It's too simple to say , Pay attention to discretization 1e9 The scope of the .

Let's see first $easy$$version$, The meaning of the title is to give you a palindrome string , You can do two things , Put one 0 become 1 Or skip this round （ If and only if the current is not a palindrome string ）.
Easy to know, only with 0 The quantity is related to .

$$n=1,afterhandwin$$

$$n=p.Count$$
Because I know that the middle element is 0, Let's take the middle element first .
$$0001000$$
Then the second person can't flip , Because this time is palindrome string , No problem , We choose symmetrically with him .
$$0111220$$
In the last two, we flip
$$2111222$$
So when you know odd numbers, you will win first . And take the lead 1 Cost .

$$n=accidentallyCount$$
Empathy , After the last round, turn your hands , The second is the winner . And the backhand is ahead 2 Cost .

Look again. $hard$$version$
Because this time is not a palindrome string , First, calculate the distance between the string and the palindrome string dis.
The first hand naturally leads the second dis Cost
When dis>2, Win first , Because the first hand is the worst 2 Cost
When dis=0, Back to the palindrome string
When dis=1, And there are only two 0 It ends in a draw
When dis=1, And there are more than two 0, Win first , Although in palindromes, we know that even numbers lead 2, But we can choose not to skip the last round , Exchange first, then hand
When dis=2, Because there is an operation of exchanging first and then , The first step is to win

Baby this inscription has been written for a long time , May be old crying crying

#include<bits/stdc++.h>
using namespace std;
int len;
char s[100005];
int main()
{
    
	int t;
	scanf("%d",&t);
	while(t--)
	{
    
	    int cnt=0,cnt0=0;
	    scanf("%d",&len);
		scanf("%s",s+1);
		for(int i=1;i<=len;i++)if(s[i]=='1'&&s[len-i+1]=='0')cnt++;
        for(int i=1;i<=len;i++)if(s[i]=='0')cnt0++;
        if(cnt>2)printf("ALICE\n");
        else
        {
    
            if(cnt==0)
            {
    
                cnt=cnt0;
                if(cnt%2==1)
                {
    
                    if(cnt==1)printf("BOB\n");
                    else printf("ALICE\n");
                }
                else printf("BOB\n");
            }
            else if(cnt==1)
            {
    
                cnt=cnt0-cnt;
                if(cnt==0)printf("ALICE\n");
                else if(cnt%2==1)
                {
    
                    if(cnt==1)printf("DRAW\n");
                    else printf("ALICE\n");
                }
                else printf("ALICE\n");
            }
            else if(cnt==2)
            {
    
                cnt=cnt0-cnt;
                if(cnt==0)printf("ALICE\n");
                else if(cnt==1)printf("ALICE\n");
                else if(cnt%2==1)printf("ALICE\n");
                else printf("ALICE\n");
            }

        }

	}
	return 0;
}