题解

异或性质

异或运算满足：

• $x\oplus x=0$；
• $x\oplus0=x$；
• 交换律和结合律成立。

把全部筷子长度异或起来，每一对相同长度都会互相抵消为 $0$，最终只剩下落单筷子的长度。

程序只需要一个变量 ans，读入一个数就执行：

ans ^= x

由于 $n$ 很大且内存限制紧，应边读边计算，不要建立长度为 $n$ 的数组。标程使用快速读入。

正确性说明

将所有输入按相同长度重新分组不会改变异或结果，因为异或满足交换律和结合律。每一对相同值的异或结果为 $0$，所有成对元素全部消失，最后的结果就是唯一未配对的值。

复杂度

• 时间复杂度：$O(n)$；
• 额外空间复杂度：$O(1)$。