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次方来减去数组中的某个数，再来找数组中是否有这个数是关键，如果用循环来遍历的话，很可能会超时。
