丢失的练习册

题目

by Xinran Fang

描述

每个人有 3 本练习册. 现有 N 个人的练习册混在一起且少了一本. 为了找到谁少了一本, 一本一本的记录上面的学号, 请据此编程求出这个人的学号.

提示:

  • 取值范围:
    • N 取 \(\left[1, 10^6\right]\);
    • 学号取 \(\left[0, 2 \times 10^9\right]\);
  • 测试样例:
    • 1~3测试样例 N \(<1 \times 10^4\);
    • 4~5测试样例 \(1 \times 10^4 \leq\) N \(\leq 5 \times 10^5\);
    • 6~10测试样例 \(5 \times 10^5 \leq\) N \(\leq 1 \times 10^6\);
  • 时间和空间:
    • 时间 O(n)、空间 O(1).

IO格式

输入:

N
第1本练习册上的学号
...

输出:

缺一本练习册的人的学号

样例

输入:

3
2021001
2021001
2023002
2023003
2023002
2023003
2023002
2021001

输出:

2023003

解答

思路

时间 O(1), 那就必须采取流式的处理方法. 注意到这里有一个特殊的性质——每人有 3 本练习册, 在二进制下, 这意味着数的各位和应当为 3 的倍数; 而缺 1 本的人, 会在每个是 1 的位上产生 2 的余数, 据此可求.

代码

#include <array>
#include <bitset>
#include <iostream>
using namespace std;

using ui = unsigned int;
constexpr size_t uiBitNum = sizeof(ui) * 8;

// 位和
static array<ui, uiBitNum> bitsSum;

// 处理
void f(ui cur) {
    bitset<uiBitNum> temp(cur);
    for (auto i = 0; i < uiBitNum; i++) {
        bitsSum[i] += temp[i];
    }
}

int main() {
    ios::sync_with_stdio(false);
    // 输入
    ui n, cur;
    cin >> n;
    for (auto i = 0; i < 3 * n - 1; i++) {
        cin >> cur;
        f(cur);
    }
    // 输出
    bitset<uiBitNum> bits;
    for (auto i = 0; i < uiBitNum; i++) {
        bits[i] = bool(bitsSum[i] % 3);
    }
    cout << ui(bits.to_ulong());
    return 0;
}

时空消耗

1	Accepted	0 ms	1516 KB
2	Accepted	0 ms	1524 KB
3	Accepted	4 ms	1524 KB
4	Accepted	40 ms	1520 KB
5	Accepted	84 ms	1524 KB
6	Accepted	212 ms	1520 KB
7	Accepted	456 ms	1520 KB
8	Accepted	432 ms	1520 KB
9	Accepted	456 ms	1520 KB
10	Accepted	456 ms	1524 KB