【例45.2】 筷子大作战

解题思路

把全部筷子长度异或。相同的两只长度异或为0，成对的全部抵消，只剩落单长度。

正确性说明

计算规则直接来自题目定义。按所述顺序处理时，已完成部分的结果被准确保存在累加量、计数或当前状态中；下一步只加入新增贡献。最终得到完整要求的结果。

易错点

无需排序或数组，可边读边异或，适合五百万数据。

复杂度

时间O(n)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

异或满足交换结合律、x ^ x =
    0、x ^ 0 = x；所有偶数个同长度消去，唯一奇数个长度保留下来。 int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int ans = 0;
    while (n--) {
        int x;
        cin >> x;
        ans ^= x;
    }
    cout << ans << "\n";
    return 0;
}