本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-16 06:00:04

先找性质。

由于 $1,2,3$ 无论怎么 $\oplus$ 都凑不出来 $4$，所以要合法，必须让 $4$ 的个数为偶数。

然后又 $1 \oplus 2 = 3$，所以一个 $1$ 和一个 $2$ 可以和一个 $3$ 抵消，所以 $1,2,3$ 的个数奇偶性相同。

然后考虑预处理，由于 $1,2,3$ 的次数贡献跟 $4$ 无关，所以预处理的时候不用考虑 $4$。

那么设 $f_{i,j,k}$ 表示 $i$ 个 $1$，$j$ 个 $2$，$k$ 个 $3$ 的最大赢得次数，并且 $i, j, k$ 奇偶性相同，那么我们要么选出两个相同的数，然后异或抵消，要么选择 $1,2,3$ 并抵消，即 $f_{i,j,k} = \min\{ f_{i-2,j,k},f_{i,j-2,k}, f_{i,j,k-2},f_{i-1,j-1,k-1} \} + 1$。

然后询问的时候分别将 $a,b,c$ 变为同奇或同偶然后取最大即可。

#include <bits\/stdc++.h>
 
using namespace std;
 
int T;
int f[210][210][210];
 
int main() {
	f[1][1][1] = 1;
	for (int i = 0; i <= 200; ++i) {
		for (int j = (i & 1); j <= 200; j += 2) {
			for(int k = (j & 1); k <= 200; k += 2) {
				if (i == 1 && j == 1 && k == 1) continue;
				if (i == 0 && j == 0 && k == 0) continue;
				if (i >= 2) f[i][j][k] = max(f[i][j][k], f[i - 2][j][k] + 1);
				if (j >= 2) f[i][j][k] = max(f[i][j][k], f[i][j - 2][k] + 1);
				if (k >= 2) f[i][j][k] = max(f[i][j][k], f[i][j][k - 2] + 1);
				if (i >= 1 && j >= 1 && k >= 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 1] + 1);
			}
		}
	}
 
	scanf("%d", &T);
	while (T--) {
		int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
 
		int ans = 0;
		if (a - (a & 1) >= 0 && b - (b & 1) >= 0 && c - (c & 1) >= 0) ans = f[a - (a & 1)][b - (b & 1)][c - (c & 1)];
		if (a - (!(a & 1)) >= 0 && b - (!(b & 1)) >= 0 && (c - (!(c & 1))) >= 0) ans = max(ans, f[a - (!(a & 1))][b - (!(b & 1))][(c - (!(c & 1)))]);
 
		printf("%d\n", d \/ 2 + ans);
	}
	return 0;
}