B4241 [海淀区小学组 2025] 统计数对

· · 题解

欢迎报名洛谷网校，期待和大家一起进步！

本题考察 map 的使用。

题目询问有多少个数对满足 a_i+a_j=2^x，直接枚举 (i,j)，判断其是否是 2 的幂次，则时间复杂度是 O(n^2) 或者 O(n^2 \log V) 的（V 表示 a_i 的值域，是否有 \log V 取决于是否使用位运算 x & (x - 1) 判断正整数 x 是否是 2 的幂次），只能通过 40\% 的数据。

不妨移项，有 a_j=2^x-a_i。接着我们枚举 i 和 x，即可计算出 2^x-a_i。接着我们判断 a_j 是否有出现过即可。这一步就需要使用 map。具体而言，使用 map <int, int> m 存储 a_i 这个值出现的次数。这样，我们只需统计 2^x-a_i 出现了多少次，将这个次数累加进答案中即可。

接下来演示一个经典的错误写法：

for (int i = 1; i <= n; i++) {
    m[a[i]]--;
    for (int j = 0; j <= 30; j++)
        ans += m[(1 << j) - a[i]];
}

在这份代码中确实是在枚举 i 和 x，得知 2^x-a_i 的出现次数并且加到答案，同时也通过 m[a[i]]-- 的方式避免重复统计，但是这一份代码提交只能获得部分分数。这是因为若是直接访问 map 下标，此时如果 2^x-a_i 不存在值，则会新建一个下标 2^x-a_i，值为 0。这样一来，这个 map 容器中就会存在 O(n\log V) 个元素（\log V 在本题中为 31），单次访问时间复杂度为 O(\log (n \log V))，总复杂度为 O(n \log V \log (n \log V))，无法通过本题。

一个更好的做法是，首先使用 m.count() 函数，判断这个下标是否在 map 中出现过。若没出现过就不管，出现过了再计算。这样可以避免反复地新建下标。由于 count 函数单次是 O(\log n) 的，因此时间复杂度为 O(n \log V \log n)，可以通过本题。

参考代码：

for (int i = 1; i <= n; i++) {
    m[a[i]]--;
    for (int j = 0; j <= 30; j++) {
        if (m.count((1 << j) - a[i]))
            ans += m[(1 << j) - a[i]];
    }
}