题解：CF1955F Unfair Game

· · 题解

先找性质。

由于 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;
}