取石子

题目链接：NOI2022省选挑战赛 Contest3 C

题目大意

给你一个序列，两个人轮流操作每次可以拿走序列两头的其中一个数。
然后谁选的数的异或和大谁就赢。
然后每次问你先手必胜还是后手必胜还是平局。

思路

首先异或嘛，肯定是按位数从高到低看。
那不难想出如果对于一位它在偶数个数中出现，那要么大家都是 \(0\)，要么都是 \(1\)。

所以我们只需要看最高位的第一个所有数异或起来不是 \(0\) 的位置，那如果全是 \(0\) 就平手。
然后问题就变成了一个 \(01\) 串（奇数个 \(1\)），每次可以取头尾，取到奇数个的获胜。

然后发现如果长度是偶数就先手必胜，因为你奇数位置和偶数位置 \(1\) 的个数肯定是一奇一偶的，而且先手显然可以取最优的奇数位置或偶数位置，所以必胜。
接着看偶数长度，那先手第一步必须取 \(1\)，不然状态就变成了后手变先手，然后长度偶数，就是后手胜了。
那也因为这个条件，接下来每次先手必须取后手一样的数。

所以我们可以先枚举先手取的是头还是尾，看是否可能获胜。
然后可以这样看，先不断删去头尾相同的，然后接着序列就必须是 \(00110011....\) 这样两两弄下去（也就是每两个位置必须一样，不一定要交错，可以 \(11000011\)）

然后你还发现这样除了先手多了一个 \(1\)，它们取的数量是 \(\frac{cnt-1}{2}\)（\(cnt\) 是整个序列中 \(1\) 的个数），因此我们这时候还需要保证这个值是一个偶数（这样先手加上一开始拿的才会有奇数个）。

然后就好了。

代码

#include<cstdio>

using namespace std;

int t, n, a[10001];

bool check(int l, int r) {
	while (l <= r && a[l] == a[r]) l++, r--;
	for (int i = l; i <= r; i += 2)
		if (a[i] != a[i + 1]) return 0;
	return 1;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		int va = 0; for (int i = 1; i <= n; i++) scanf("%d", &a[i]), va ^= a[i];
		if (!va) {
			printf("Draw\n"); continue;
		}
		for (int i = 30; i >= 0; i--) {
			if (!((va >> i) & 1)) continue;
			int cnt = 0;
			for (int j = 1; j <= n; j++) {
				a[j] = (a[j] >> i) & 1;
				if (a[j]) cnt++;
			}
			if (n & 1) {
				if (((cnt - 1) >> 1) & 1) printf("Bob\n");
					else if ((a[1] && check(2, n)) || (a[n] && check(1, n - 1))) printf("Alice\n");
						else printf("Bob\n");
			}
			else printf("Alice\n");
			break;
		}
	}
	
	return 0;
}