题解

思路

一个序列的异或值只与四种数的数量奇偶性有关。设

$$q=\left\lfloor\frac{p_1}{2}\right\rfloor+ \left\lfloor\frac{p_2}{2}\right\rfloor+ \left\lfloor\frac{p_3}{2}\right\rfloor+ \left\lfloor\frac{p_4}{2}\right\rfloor.$$

做法

每两个相同的数可以看作一对。先处理至多四个没有配对的数，再连续移除这些数对，就能让每一对恰好贡献一次 Bob 获胜，因此基础答案为 $q$。

数 $1,2,3$ 满足 $1\mathbin{\mathrm{xor}}2\mathbin{\mathrm{xor}}3=0$。当且仅当 $p_1,p_2,p_3$ 都是奇数时，三个未配对的 $1,2,3$ 可以额外形成一次异或为 $0$ 的非空状态；$p_4$ 的奇偶性不影响这个额外贡献，因为若还剩一个 $4$，可以先将它移除。

因此答案是

$$q+[p_1\bmod 2=1\land p_2\bmod 2=1\land p_3\bmod 2=1].$$

其中方括号内命题成立时取 $1$，否则取 $0$。

正确性证明

把每一类数拆成若干对相同数字和至多一个未配对数字。先移除不需要保留的未配对数字，可以使剩余数量全部为偶数。若此时仍有数，每开始处理一对相同数字时，当前异或值为 $0$；移除这对中的第一个数后异或值非零，移除第二个数后又恢复为 $0$。于是 $q$ 对数字可以构造出 $q$ 次 Bob 获胜。

若 $p_1,p_2,p_3$ 都是奇数，则保留未配对的 $1,2,3$。它们的异或值为 $0$；若还有未配对的 $4$，先移除该 $4$。这样在处理所有数对之前还能构造一次 Bob 获胜，所以可以达到 $q+1$ 次。

反过来，除上述三个未配对的 $1,2,3$ 外，每增加一次异或值为 $0$ 的非空状态，都必须至少完成一对相同数字所对应的两次奇偶翻转。这样的数对一共只有 $q$ 对。四个未配对数字中，能够产生额外零异或非空状态的唯一非空组合是 $1,2,3$，因为 $1\mathbin{\mathrm{xor}}2\mathbin{\mathrm{xor}}3=0$，而加入 $4$ 或取其余非空子集都不为 $0$。因此答案至多为 $q$，或在前三类数量全为奇数时至多为 $q+1$。

构造达到上界，上界也不能被超过，所以公式正确。

复杂度分析

每个测试用例只进行常数次整数运算，时间复杂度为 $O(1)$，额外空间复杂度为 $O(1)$。