CodeForces - 1005C Summarize to the Power of Two

cf原题传送门:cf真好玩
vjudge传送门:cf真好玩

题目描述

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.

题意分析

啊，熟悉的全英文题面，虽然看起来有点吃力但还是要看的，不记得了之前在哪里听到过这样一句话，做程序员，不能排斥英语，你要学会去适应。也把这句话送给和我一样的小白白们。
其实仔细看看还是可以懂个大概的，然后就可以看样例猜题意了。这道题的意思是给你一组数，每个数都可以和另外任意一个数（不包括他自己）进行求和，如果求和之后是2的N次方，这个数就可以存在在这个数列中。如果有一个数，和其他任意一个数相加都不是2的N次方，这个数就不符合要求，题目中要求输出的就是不符合条件的数字的个数（可以为0）。我一开始想着暴力判断再慢慢优化，然后发现我的优化能力不是很强（😭逃。然后想到了map。用2的N次方减去每一个数，判断差是否存在。具体看代码实现。

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200000];
int main()
{
    map<ll,ll> ma;
    ll n,i,k,ans=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        ma[a[i]]++;//对a[i]出现的次数进行计数
    }
    for(int i=0;i<n;i++)
    {
        ll er=1,g=0,j=0;
        for(int j=0;j<31;j++)
        {
            if(ma[er-a[i]]!=0)//ma[er-a[i]]不为零说明差值在数列中存在
            {
                if(er-a[i]==a[i])//如果差值为它自己，就需要接着判断
                {
                    if(ma[a[i]]>1)
                        g++;
                }
                else    g++;
            }
            er*=2;//er就是2的N次方
        }
        if(g==0)    ans++;//g为0则说明差值不存在或者差值与a[i]相等且a[i]只出现一次，即a[i]不是符合条件的数。
    }
    cout<<ans<<endl;
    return 0;
}

小结

随着慢慢的刷题，发现这些容器，函数什么的都贼好用，解决问题的时候应该多往这方面想一想。

赏