自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:18:04，当前版本为作者最后更新于2025-03-11 11:26:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

本题考察 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]];
    }
}