CodeForces - 1005C Summarize to the Power of Two (贪心 + 离散化)

53 阅读 0 评论 35 点赞

我是靠谱客的博主闪闪西牛，最近开发中收集的这篇文章主要介绍CodeForces - 1005C Summarize to the Power of Two (贪心 + 离散化)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Summarize to the Power of Two

A sequence a1,a2,…,an is called good if, for each element ai, there exists an element aj (i≠j) such that ai+aj is a power of two (that is, 2d for some non-negative integer d).

For example, the following sequences are good:

[5,3,11] (for example, for a1=5 we can choose a2=3. Note that their sum is a power of two. Similarly, such an element can be found for a2 and a3),
[1,1,1,1023],
[7,39,89,25,89],
[].
Note that, by definition, an empty sequence (with a length of 0) is good.

For example, the following sequences are not good:

[16] (for a1=16, it is impossible to find another element aj such that their sum is a power of two),
[4,16] (for a1=4, it is impossible to find another element aj such that their sum is a power of two),
[1,3,2,8,8,8] (for a3=2, it is impossible to find another element aj such that their sum is a power of two).
You are given a sequence a1,a2,…,an. What is the minimum number of elements you need to remove to make it good? You can delete an arbitrary set of elements.

Input
The first line contains the integer n (1≤n≤120000) — the length of the given sequence.

The second line contains the sequence of integers a1,a2,…,an (1≤ai≤109).

Output
Print the minimum number of elements needed to be removed from the given sequence in order to make it good. It is possible that you need to delete all n elements, make it empty, and thus get a good sequence.

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
1 1 1 1023
Output
0
Note
In the first example, it is enough to delete one element a4=5. The remaining elements form the sequence [4,7,1,4,9], which is good.

题意：给定一个数组，问数组中每一个元素 a[i] , 是否存在另一个元素 a[j], 使 a[i] + a[j] 是 2 的次幂， i != j

思路：贪心，先打出足够的2的次幂，然后对于每一个数判断 power - a[j] 是否存在就可以了。由于数很大，用map就可以了（不过我写的lower_bound离散 ~~ORZ~~）。

AC代码：

#include<bits/stdc++.h>
#define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl
#define pii pair<int,int>
#define clr(a,b) memset((a),b,sizeof(a))
#define rep(i,a,b) for(int i = a;i < b;i ++)
#define pb push_back
#define MP make_pair
#define LL long long
#define INT(t) int t; scanf("%d",&t)
#define LLI(t) LL t; scanf("%I64d",&t)
using namespace std;
const int maxn = 120010;
int vis[maxn];
LL power2[32];
int a[maxn];
int b[maxn];
int main()
{
power2[0] = 1;
rep(i,1,32)
power2[i] = power2[i - 1] * 2;
int n;
while(~scanf("%d",&n)){
memset(vis,0,sizeof(vis));
rep(i,0,n){ scanf("%d",&a[i]); b[i] = a[i]; }
sort(b,b + n);
sort(a,a + n);
int f = unique(b,b + n) - b;
rep(i,0,n){
int x = lower_bound(b,b + f,a[i]) - b;
//debug(x);
++ vis[x];
}
int ans = 0;
rep(i,0,n){
int x = lower_bound(b,b + f,a[i]) - b;
int y;
int flag = 0;
rep(j,0,32){
y = lower_bound(b,b + f,power2[j] - a[i]) - b;
if(b[x] + b[y] == power2[j]){
if(x != y || (x == y && vis[x] > 1)){
flag = 1;
break;
}
}
}
if(!flag){ ++ ans; }
}
printf("%dn",ans);
}
return 0;
}