BISHI32　被打乱的异或和¶

简单通过率 76.8%python3样例通过牛客 AC

牛客原题　源码

讲解章节：运算符与位运算、位运算

一句话

数组里混进了「其余元素的异或和 x」，把 x 找回来。

解题思路¶

这题考什么¶

异或的自反性 a xor a = 0。原数组 b 长度 n-1，x = b_1 xor ... xor b_{n-1}，把 x 追加进去之后，新数组 a 的总异或 = x xor x = 0。也就是说：给定数组的总异或恒为 0。

于是对任意下标 i，把 a_i 拿掉后剩下 n-1 个数的异或

= (总异或) xor a_i = 0 xor a_i = a_i。

这说明「随便挑哪个元素当 x 都是合法答案」——直接输出 a_1 即可，连异或都不用算。

数据规模与复杂度¶

t <= 1000，n <= 100，总元素量 <= 1e5。O(总元素量) 只花在读入上。

坑在哪¶

千万别去输出「全体异或」——那恒等于 0，只有恰好 x = 0 的组才对；
答案不唯一，而且是结构性的不唯一：上面已证「拿掉任意一个元素，剩下的异或恰好等于它」，所以数组里每一个位置都是一组合法答案。样例第一组给的是 3，本解法固定输出该组的第一个元素 4，同样合法。这类题本地要用 special judge（特殊评测程序，按题目条件验证选手输出是否合法，而不是与标准答案逐字符比对）：本题配了 solutions/_spj/BISHI32.py，它验证「输出值确实在数组中出现过，且删掉它一个之后剩余元素的异或等于它」；
多组数据，用 buffer.read().split() 一次读完 + 游标推进最省时间。

参考实现¶

solutions/BISHI32.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    p = 1
    out = []
    for _ in range(t):
        n = int(data[p])                  # n 只用来推进游标，不参与计算
        p += 1
        out.append(str(int(data[p])))     # 任取一个元素即为合法的 x，这里取第一个
        p += n                            # 本组剩下的数无需读取，游标直接跳过整段
    sys.stdout.write("\n".join(out) + "\n")


main()

BISHI32 被打乱的异或和¶