Unfair Game | Serendipity

type

status

date

slug

summary

题目描述

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

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

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

输入描述

第一行包含一个整数—测试用例数。

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

输出描述

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

示例

输入

输出

说明

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

在第二个例子中，如果夏娃删除了一个 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}和{ }。以上几种情况只有第一种会是最终结果加1，对应到最初状态就是1，2，3的个数都为奇数个。

下面给出完整代码：