Codeforces Round #721 (Div. 2) B2. Palindrome Game (hard version)

来自某个废物时隔n天的补题
我怎么这么菜.jpg
有了B1的经验，我们很容易想到对于长度奇偶的分类
首先明确两件事情（根据B1）：

1. 回文时，偶数后手必胜
2. 回文时，奇数中间是1或者有n-1个1的时候后手必胜，中间为0且不是n-1个1时时先手必胜
   基于上面两点，很容易扩展到这道题（真的吗？）
3. 对于长度为偶数，或者中间那个是1的奇数的字符串，且此时不是回文，Alice可以先不停的旋转，直到马上是回文了，Alice操作让这个字符串变成回文，然后BOB就得到了上面1的情况，此时Alice的花费只有1。（注意一点，就是如果变成了回文之后就全是1了，那Alice一直转就可以了，花费为0，也会胜利，所以此时Alice必胜）
4. 对于中间那个是0的字符串，且不是回文，Alice还是不停的旋转，直到已经是回文了（但是中间是0），或者马上是回文了，Alice让它变成（或者保持回文），然后BOB得到了2的情况，Alice花费为1，但是如果BOB操作一次就得到了这个局面，那就是DRAW（平局），否则ALICE赢。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
char s[N];
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		scanf("%s", s + 1);
		int cnt = 0, cnt1 = 0;
		for (int i = 1; i <= n - i + 1; i++)
			if (s[i] != s[n - i + 1])
				cnt++;
		for (int i = 1; i <= n; i++)
			if (s[i] == ‘1‘)	cnt1++;
		if (n % 2 == 0 || s[n / 2 + 1] == ‘1‘) {
			if (cnt == 0)	puts("BOB");
			else puts("ALICE");
		}
		else {
			if (cnt == 0 && cnt1 == n - 1)	puts("BOB");
			else if (cnt == 1 && cnt1 == n - 2)	puts("DRAW");
			else puts("ALICE");
		}
	}
	return 0;
}

Codeforces Round #721 (Div. 2) B2. Palindrome Game (hard version)

原文：https://www.cnblogs.com/cminus/p/14832276.html