CodeForces 702B: Powers of Two（遍历、穷举）

  The first line contains the single positive integer n (1 ≤ n ≤ 105) — the number of integers.

  The second line contains n positive integers $a_1, a_2, ..., a_n$ (1 ≤ $a_i$ ≤ 109).

Output

  Print the number of pairs of indexes i, j (i < j) that $a_i + a_j$ is a power of 2.

Simple Input

4
7 3 2 1
3
1 1 1

Simple Output

2
3

Note
  In the first example the following pairs of indexes include in answer: (1, 4) and (2, 4).
  In the second example all pairs of indexes (i, j) (where i < j) include in answer.

Code 1
思路：遍历查找

//时间复杂度太高，当输入数据组数较多时会超时
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
#define maxn 100005
LL a[maxn]={0};

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int sum=0;
        for(int i=0; i<n; i++)
            scanf("%lld",&a[i]);
        for(int i=0; i<n-1; i++)
            for(int j=i+1; j<n; j++){
                LL x=1;
                for(int k=0; k<=31; k++)
                    {
                        if(a[i]+a[j]==x) {sum++;break;}
                        x=x<<1;
                    }
            }
        printf("%dn",sum);
    }
    return 0;
}

Code 2
思路：利用$a_i+a_j=2^x$关系枚举 x <script id="MathJax-Element-8" type="math/tex">x</script>

#include<bits/stdc++.h>
using namespace std;
#define LL long long
map<LL,int>a;           //映射到int的初始值是零
LL sum=0;

int main()
{
    int n;
    while(~scanf("%d",&n)){
    for(int i=0; i<n; i++)
    {
        LL x;
        scanf("%lld",&x);
        for(int j=0; j<=31; j++)
            sum+=a[(1LL<<j)-x];     //由ai+aj=2^x枚举x,若对应LL非空，则加上其映射值int
        a[x]++;                     //用int记录对应LL出现的次数
    }
    printf("%lldn",sum);
    }
    return 0;
}

最后

以上就是优雅鸵鸟为你收集整理的CodeForces 702B: Powers of Two（遍历、穷举）的全部内容，希望文章能够帮你解决CodeForces 702B: Powers of Two（遍历、穷举）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。