传送门：洛谷 Vlad and Division | Codeforces D. Vlad and Divison

更佳的阅读体验：CF1926D 题解

简要题意：两个二进制下第 $1$ 到 $31$ 位都不同的数可以组合成一组，一个单独的数也可以成为一组。有 $n$ 个数，求最少可以构成多少组。

二进制下，每一位只可能是 $0$ 或 $1$，所以对于一个数，在二进制下 $1$ 到 $31$ 位都不同的数是唯一的，并且这两个数的和是一定的，即 $2147483647$（$2^{31} - 1$）。

考虑使用 map 维护每个数出现的数量。读入时存下每个数的数量，然后遍历整个序列，如果发现当前数 $a_i$ 和 $2147483647 - a_i$ 都有出现，那么即可贪心地凑成一对。

#include <iostream>
#include <map>
using namespace std;
using ll = long long;

const int N = 2e5 + 10, LIM = 2147483647;
int t, n, a[N], ans;
map<int, int> mp;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        ans = 0, mp.clear();
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i], ++mp[a[i]];
        for (int i = 1; i <= n; ++i) if (mp[a[i]]) {
            --mp[a[i]];
            if (mp[LIM - a[i]]) --mp[LIM - a[i]];
            ++ans;
        } cout << ans << '\n';
    } return 0;
}

后记

没事别用 unordered_map，血的教训。