Summarize to the Power of Two（map+思维）-白红宇

Summarize to the Power of Two（map+思维）

阅读量：5034 次

发布时间：2019-06-12

本文共 2890 字，大约阅读时间需要 9 分钟。

A sequence ${a1,a2,\dots,ana1,a2,\dots,an is called good if, for each element aiai, there exists an element ajaj (i\neqji\neqj) such that ai+ajai+aj is a power of two (that is, 2d2d for some non-negative integer dd).}_{1,a2,\dots,ana1,a2,\dots,an is called good if, for each element aiai, there exists an element ajaj (i\neqji\neqj) such that ai+ajai+aj is a power of two (that is, 2d2d for some non-negative integer dd).}$

For example, the following sequences are good:

$[5,3,11][5,3,11] (for example, for a1=5a1=5 we can choose a2=3a2=3. Note that their sum is a power of two. Similarly, such an element can be found for a2a2 and a3a3),$

$[1,1,1,1023][1,1,1,1023],$

$[7,39,89,25,89][7,39,89,25,89],$

$[][].$

Note that, by definition, an empty sequence (with a length of $00) is good.$

For example, the following sequences are not good:

$[16][16] (for a1=16a1=16, it is impossible to find another element ajaj such that their sum is a power of two),$

$[4,16][4,16] (for a1=4a1=4, it is impossible to find another element ajaj such that their sum is a power of two),$

$[1,3,2,8,8,8][1,3,2,8,8,8] (for a3=2a3=2, it is impossible to find another element ajaj such that their sum is a power of two).$

You are given a sequence ${a1,a2,\dots,ana1,a2,\dots,an. What is the minimum number of elements you need to remove to make it good? You can delete an arbitrary set of elements.}_{1,a2,\dots,ana1,a2,\dots,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 $nn (1\leqn\leq1200001\leqn\leq120000) — the length of the given sequence.$

The second line contains the sequence of integers ${a1,a2,\dots,ana1,a2,\dots,an (1\leqai\leq1091\leqai\leq109).}_{1,a2,\dots,ana1,a2,\dots,an (1\leqai\leq1091\leqai\leq109).}$

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 $nn elements, make it empty, and thus get a good sequence.$

Examples

input

6 4 7 1 5 4 9

output

input

5 1 2 3 4 5

output

Copy

input

1 16

output

input

4 1 1 1 1023

output

Note

In he first example, it is enough to delete one element ${a4=5. The remaining elements form the sequence [4,7,1,4,9][4,7,1,4,9], which is good.}_{4=5. The remaining elements form the sequence [4,7,1,4,9][4,7,1,4,9], which is good.}$

题目意思：给你一个数列，然后让你删掉某个数，让每一个数都可以与另外一个数相加，之和等于2的^d次方，问最少删掉的个数

解题思路：先预处理出2的次幂，然后暴力枚举出每个数与每个2的次幂之差，去判断在map中是否有这样的差存在（注意相同的两个数，比如4 ，4 这个时候就可以特判一下，出现次数），若不存在那么就需要删除掉这个数。

1 #include
        
          2 #include
         
           3 #include
           4 #include
           
             5 #define ll long long int 6 using namespace std; 7 ll d[32]; 8 ll a[1000010]; 9 map
            
             mp;10 void double_2()11 {12     int i;13     d[0]=1;14     for(i=1; i<=31; i++)15     {16         d[i]=d[i-1]*2;17     }18 }19 int main()20 {21     int i,j,flag,n;22     ll k;23     double_2();///2的幂24     while(scanf("%d",&n)!=EOF)25     {26         int count=0;27         mp.clear();///map清零28         for(i=0; i
             
              =d[j])39 {40 continue;41 }42 else43 {44 k=d[j]-a[i];45 if(mp[k])///map中存在46 {47 if(a[i]==k)48 {49 if(mp[k]>=2)///map中需要至少两个50 {51 flag=1;52 break;53 }54 }55 else56 {57 flag=1;58 break;59 }60 }61 }62 }63 if(!flag)64 {65 count++;66 }67 }68 printf("%d\n",count);69 }70 return 0;71 }

转载于:https://www.cnblogs.com/wkfvawl/p/9402498.html

你可能感兴趣的文章