找筷子

题意

给出奇数根筷子的长度。除了一个长度出现奇数次，其余长度都出现偶数次，求落单筷子的长度。

数据范围的两个重点是： $n\leqslant 10^7+1$ ，空间限制只有 8 MB。程序既不能保存全部筷子，也要控制输入开销。

思路

朴素统计为什么不合适

最直接的方法是用映射记录每个长度出现次数的奇偶性：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-19 11:59
 * update_at: 2026-07-19 11:59
 */
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据朴素解，统计每个长度出现次数的奇偶性。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    map<int, int> parity;
    for (int i = 1; i <= n; i++) {
        int length;
        cin >> length;
        parity[length] ^= 1;
    }

    for (map<int, int>::iterator it = parity.begin(); it != parity.end(); it++) {
        if (it->second == 1) {
            cout << it->first << '\n';
            break;
        }
    }
    return 0;
}

这个做法适合小数据验证，但 map 的每个节点都要保存键、值、指针和管理信息。长度种类很多时，它无法满足 8 MB 空间限制。

用异或让所有成对长度消失

异或满足：

x\mathbin{\operatorname{xor}}x=0,\qquad x\mathbin{\operatorname{xor}}0=x.

异或还满足交换律和结合律，所以输入顺序不影响结果。把所有长度异或起来，每个出现偶数次的长度都会两两抵消，最终只剩出现奇数次的落单长度。

例如样例中的异或结果可以重新分组为：

(1\mathbin{\operatorname{xor}}1) \mathbin{\operatorname{xor}} (3\mathbin{\operatorname{xor}}3\mathbin{\operatorname{xor}}3\mathbin{\operatorname{xor}}3) \mathbin{\operatorname{xor}} (2\mathbin{\operatorname{xor}}2\mathbin{\operatorname{xor}}2)=2.

整个算法只需要一个答案变量，不需要知道某个长度此前出现过多少次。

为什么还要手写快速读入

本题要读取一千多万个整数。即使算法是 $O(n)$ ，逐个使用高层输入操作也可能让时间消耗集中在解析字符上。

C++ 正解使用 fread 每次读入一个固定大小的字节块，再在块内解析十进制整数。解析器只保存：

一个 64 KB 输入缓冲区；
当前缓冲区位置和有效长度；
当前整数与异或答案。

因此总内存不随 $n$ 增长。原 main.py 虽然也尝试分块读取，但仍要在 Python 层逐字节循环和反复 yield 一千多万个整数；同时 Python 运行时本身也不适合 8 MB 的严格内存限制，所以改用 C++ 流式解析。

正确性说明

设落单长度为 $y$ 。对任意其它长度 $x$ ，它出现偶数次，这些 $x$ 按两两配对后异或结果都是 $0$ 。由于异或满足交换律和结合律，可以先消去所有这样的偶数次长度。

长度 $y$ 出现奇数次，其中偶数个 $y$ 同样两两消去，最后还剩一个 $y$ 。再与其它长度留下的 $0$ 异或，最终答案就是 $y$ 。

快速读入只改变整数从输入字节中被取出的方式，不改变整数顺序和数值；主循环恰好读取并异或 $n$ 个长度，因此算法正确。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-19 11:59
 * update_at: 2026-07-19 11:59
 */
#include <cstdio>

const int BUFFER_SIZE = 1 << 16;

char input_buffer[BUFFER_SIZE];
int buffer_position;
int buffer_length;

bool read_integer(int &value) {
    char current;

    do {
        if (buffer_position == buffer_length) {
            buffer_length = fread(input_buffer, 1, BUFFER_SIZE, stdin);
            buffer_position = 0;
            if (buffer_length == 0) return false;
        }
        current = input_buffer[buffer_position++];
    } while (current < '0' || current > '9');

    value = 0;
    while (current >= '0' && current <= '9') {
        value = value * 10 + current - '0';
        if (buffer_position == buffer_length) {
            buffer_length = fread(input_buffer, 1, BUFFER_SIZE, stdin);
            buffer_position = 0;
            if (buffer_length == 0) return true;
        }
        current = input_buffer[buffer_position++];
    }
    return true;
}

int main() {
    int n;
    read_integer(n);

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        int length;
        read_integer(length);
        answer ^= length;
    }

    printf("%d\n", answer);
    return 0;
}

复杂度

每根筷子只参与一次异或，时间复杂度为 $O(n)$ ；从输入字节角度看，每个字节也只扫描一次。
除固定的 64 KB 输入缓冲区外，只使用常数个整数，额外空间复杂度为 $O(1)$ 。
brute.cpp 使用映射，时间复杂度为 $O(n\log n)$ ，空间复杂度为 $O(n)$ ，仅用于小数据验证。

本机用 $10{,}000{,}001$ 个长度构造最大规模输入，C++ 程序约 0.05s 完成，采样峰值 RSS 为 3712 KB；具体时间随机器变化，但内存规模稳定低于题目限制。

总结

本题的算法核心是“偶数次出现可以用异或消去”，工程核心则是“不能保存数据，也不能让输入解析成为瓶颈”。一个异或变量配合固定大小的 fread 缓冲区，能够同时满足千万数据和 8 MB 空间限制。

目录

题意

思路

朴素统计为什么不合适

用异或让所有成对长度消失

为什么还要手写快速读入

正确性说明

代码

复杂度

总结