本题思路:
暴力枚举枚举每个d的情况 根据题目中的数据判断a[i]<=1e9 而2的30次方大约是1e9 最多也就是两个2^30 变成2^31
那么枚举32次就够了 每次寻找是否可以搭配的数字 倘若没有找到就删除掉这个数字(代码附有详细注释 请见代码)
题目描述
(中文翻译版本)
一个序列a1, a2, …, an被称为好的序列,当且仅当这个对于这个序列中的每一个元素ai都存在另一个元素aj使得ai+aj=2d,d为任意的非负整数。 举个例子,下面这些序列是好的序列
[6, 2, 10] (当a1=6可以选择a2=2. 则有2+6=8=23。类似地,a2和a3也能找到与2的次幂互补的数),
[5, 5, 1019, 5],
[7, 39, 89, 25, 89],
[].
注意:按照定义,空序列也是好的
现在你有一个序列a1, a2, …, an. 你需要排除最少的数使整个序列是好的
Input
第一行包含一个整数n(1 ≤ n ≤ 120000)表示序列的总长度. 第二行包含一个序列a1, a2, …, an (1 ≤ ai ≤ 109).
Output
一行输出一个数表示使序列变好最少需要删除的数字数量。 注意,你可能需要删除整个串来使序列变好。
样例
Examples
Input
6
4 7 1 5 4 9
Output
1
Input
5
1 2 3 4 5
Output
2
Input
1
16
Output
1
Input
4
5 5 1019 5
Output
0
Note
再第一个样例中, 你只需要删除a4。则剩下的序列为[4, 7, 1, 4, 9]是一个好的序列
C++ 代码
#include<iostream>
#include <map>
const int N=120000+10;
using namespace std;
map<long long,long long> m;//数据范围太大了 因此要用到map
long long n,a[N];
long long ans=0;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
m[a[i]]++;//记录相应的个数
}
for(int i=0;i<n;i++)
{
long long l=1,k=0;
for(int j=0;j<32;j++)//2的30次方大约是1e9 最多也就是两个2^30 变成2^31
{
if(m[l-a[i]]!=0) //如果序列中存在这样的数
{
if(l-a[i]==a[i])
{
if(m[a[i]]>1) k++; //确保那个l-a[i]的数并不是自己 k>1说明有搭配
}
else k++; //找得到搭配
}
l*=2;//找下一个次方数了
}
if(k==0) ans++;//循环一圈找不到搭配那么就删除这个数字
}
cout<<ans<<endl;
return 0;
}