Unfair Game

题目连接：

Problem - F - Codeforces

---

题目描述

爱丽丝和鲍勃在傍晚时分聚集在一起，就一个由 $n$ 个整数组成的数列玩了一个刺激的游戏，数列中的每个整数都不超过 4。游戏规则太复杂，无法描述，所以我们只描述获胜条件——如果序列中所有数字的比特XOR都非零，则爱丽丝获胜；否则，鲍勃获胜。

他们邀请夏娃担任裁判。一开始，爱丽丝和鲍勃用 $n$ 个数字进行游戏。一局游戏结束后，夏娃从序列中移除一个数字，然后爱丽丝和鲍勃用 $n-1$ 个数字进行游戏。夏娃再次删除一个数字，然后爱丽丝和鲍勃使用 $n - 2$ 个数字进行游戏。这个过程一直持续到数字序列为空为止。

夏娃似乎认为在这样的游戏中，爱丽丝几乎总是赢，所以她希望鲍勃赢的次数越多越好。如果夏娃以最佳方式移除数字，求鲍勃能赢爱丽丝的最大次数。

输入描述

第一行包含一个整数 $t ( 1 \le t \le 10^4 )$ —测试用例数。

每个测试用例的第一行也是唯一一行包含四个整数 $p_i ( 0 \le p_i \le 200 )$ — 游戏开始时序列中 1、2、3 和 4 的个数。

输出描述

对于每个测试案例，如果夏娃以最佳方式移除数字，则另起一行打印鲍勃获胜的最大次数。

示例

输入

text

5
1 1 1 0
1 0 1 2
2 2 2 0
3 3 2 0
0 9 9 9

输出

text

1
1
3
3
12

说明

在第一个例子中，当夏娃还没有删除任何数字时，鲍勃获胜。

在第二个例子中，如果夏娃删除了一个 1 和一个 3，则鲍勃获胜。

---

题解

首先我们知道1，2，3，4的二进制分别为001，010，011，100，对于这几个数来说，异或（相同为0，不同为1）能出现0的组合为：

• 1，2，3的异或
• 任意一个数和自己的异或

也就是说数字4只能和自己配对，数字1，2，3有两种配对方式，但是我们思考一下，自己和自己配对能赢的次数会比1，2，3一起配对赢的次数多，也就是说，在两种方式都可以的情况下，我们优先让数字自己和自己配对。那么，我们可以先完成自己和自己配对的部分，即ans+=a/2+b/2+c/2+d/2，接下来考虑剩下不能配对的情况，有一下几种：{1，2，3}、{1，2}，{1，3}、{2，3}、{1}、{2}、{3}和{ $\emptyset$ }。以上几种情况只有第一种会是最终结果加1，对应到最初状态就是1，2，3的个数都为奇数个。

下面给出完整代码：

#include<bits/stdc++.h>
using namespace std;
int check(int a,int b,int c) // 判断奇数个数
{
    int ans=0;
    if (a%2==1)
    {
        ans++;
    }
    if (b%2==1)
    {
        ans++;
    }
    if (c%2==1)
    {
        ans++;
    }
    return ans;
}
void solve()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int ans=0;
    if (check(a,b,c)==3)
    {
        ans++;
    }
    ans+=a/2+b/2+c/2+d/2; // d独立于a,b,c
    cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;
    while (t)
    {
        solve();
        t--;
    }
    return 0;
}