Codeforces Round #496 (Div. 3)--C. Summarize to the Power of Two(没错！用的map!!,哇咔咔咔~~）

77 阅读 0 评论 51 点赞

我是靠谱客的博主勤奋钥匙，最近开发中收集的这篇文章主要介绍Codeforces Round #496 (Div. 3)--C. Summarize to the Power of Two(没错！用的map!!,哇咔咔咔~~），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A sequence $a_{1}, a_{2}, \dots, a_{n}$ is called good if, for each element $a_{i}$ , there exists an element $a_{j}$ ( $i \neq j$ ) such that $a_{i} + a_{j}$ is a power of two (that is, $2^{d}$ for some non-negative integer $d$ ).

For example, the following sequences are good:

$[5, 3, 11]$ (for example, for $a_{1} = 5$ we can choose $a_{2} = 3$ . Note that their sum is a power of two. Similarly, such an element can be found for $a_{2}$ and $a_{3}$ ),
$[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 $a_{1} = 16$ , it is impossible to find another element $a_{j}$ such that their sum is a power of two),
$[4, 16]$ (for $a_{1} = 4$ , it is impossible to find another element $a_{j}$ such that their sum is a power of two),
$[1, 3, 2, 8, 8, 8]$ (for $a_{3} = 2$ , it is impossible to find another element $a_{j}$ such that their sum is a power of two).

You are given a sequence $a_{1}, a_{2}, \dots, a_{n}$ . 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 \leq n \leq 120000$ ) — the length of the given sequence.

The second line contains the sequence of integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ).

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 
    
      Copy 
    
6
4 7 1 5 4 9

     output 
    
      Copy 
    
1

     input 
    
      Copy 
    
5
1 2 3 4 5

     output 
    
      Copy 
    
2

     input 
    
      Copy 
    
1
16

     output 
    
      Copy 
    
1

     input 
    
      Copy 
    
4
1 1 1 1023

     output 
    
      Copy 
    
0

Note

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

题意：给一组数据，如果一个数和其他数相加，不是2的某一次方，那么就删去这个数，统计需要删去的个数。

思路：因为 2^28 > 1e9. 因此我们先用一个数组把 2 的这些次方存下来。

把输入的数用map标记一下，这样我们在后面循环找的时候，如果它被标记了就说明存在，没有的话就让ans++即可。。。。

所以这题也可以用二分写？

emmm.......这样的时候

4 7 1 5 4 9

如果那个数本身就是2的某一次方，比如4 ，那么M[4]至少要2个才可以

如果不是，只要M[t]非0 即可。

下面代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 120000 + 10;
int a[maxn];
int p[maxn];
vector<int>V;
map<int,int>M;
int cnt = 0;
void init()
{
    for(int i = 0 ; i<=30 ; i++) p[i] = 1<<i; 
}
int main()
{
    int n;
    scanf("%d",&n);
    init();
    M.clear();
    for(int i = 0 ; i < n ; i++)
    {
        scanf("%d",&a[i]);
        if(!M.count(a[i]))
        {
            M[a[i]] = 1;
        }
        else 
        {
            M[a[i]] ++;
        }
    }
    int ans = 0;
    for(int i = 0 ; i < n ; i++)
    {
        int j;
        for(j = 0 ; j <= 30 ; j++)
        {
            int t = p[j] - a[i];
            if(t == a[i])
            {
                if(M[t]>=2)
                {
                    break;
                }
            }
            else 
            {
                if(M[t])
                {
                    break;
                }
            }
        }
        if(j == 31)
        {
            ans++;
        } 

    }
    cout<<ans<<endl;    
}