G题

题目大意

题目链接

给你一个大小为n的数组，对于数组中的任意一个数，如果除开这个数，在数组中能找到某个数使得两个数之和是2的d次方，那么就保留这个数，否则删除，求删除数的个数

分析

在数组中任意两数之和肯定不会超过最大的两个数之和，所以我就找到仅次于最大两个数之和的2的d次方的数m，对于数组中的每个数a，m不断除以2，看m-a这个数在数组中是否存在，如果存在的话就保留这个数，否则删除这个数，但这道题有个坑就是a=m-a的时候，这时候a的个数必须大于等于2才满足条件。数组中元素的个数为1时肯定不满足条件，所以就单独判断，直接输出1。

代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#define MAX_N 120000+3
long long num[MAX_N];
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main(int argc, char const *argv[])
{
    int cnt=0,number;
    long long mid,mid1=1;
    map<long long ,int>pq;
    memset(num,0,sizeof(num));
    scanf("%d",&number);
    for(int i=0;i<number;i++)
    {
        scanf("%lld",&num[i]);
        if(!pq.count(num[i]))
            pq[num[i]]=0;
        pq[num[i]]++;
    }
    sort(num,num+number,cmp);
    if(number==1)
    {
        cout<<"1";
        return 0;
    }
    mid=num[0]+num[1];
    for(int i=1;i,mid1<=mid;i++)
    {
        mid1*=2;
    }
    mid1/=2;
    for(int i=0;i<number;i++)
    {
        int flag=0;
        for(long long j=mid1;j>=2;j/=2)
        {
            if((j-num[i]==num[i])&&(pq[num[i]]>1))
            {
                flag=1;          
                break;
            }
            else if((j-num[i]!=num[i])&&(pq[j-num[i]]>=1))
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
            cnt++;
    }
    cout<<cnt;
    return 0;
}

总结

这道题想到用2的d次方来减去数组中的某个数，再来找数组中是否有这个数是关键，如果用循环来遍历的话，很可能会超时。