暑假练习赛1——Problem F（暴力打表）

原题链接：http://codeforces.com/problemset/problem/1005/C

Problem F

Time Limit : 6000/3000ms (Java/Other)   Memory Limit : 524288/262144K (Java/Other)

Total Submission(s) : 0   Accepted Submission(s) : 0

Problem Description

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

Input

The first line contains the integer $$$n$$$ ($$$1 \le n \le 120000$$$) the length of the given sequence.

The second line contains the sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 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.

Sample Input

6

4 7 1 5 4 9

5

1 2 3 4 5

Sample Output

1

2

===================================================================

题目大意：给出一个长度为n的整数序列，问其中有哪几项不满足题设条件（对于ai，可找到另一数aj，使得ai+aj结果为2的k次方型）。

解决思路：

如果直接模拟 求和 的话，o（10e9*10e9）的复杂度肯定爆炸，因此转换思路，求差，即用2^k减去ai，判断其结果aj是否在原数列中（可用map快速查找），因为ai+aj最大等于2*10e9，而2^31==2.147 483 648*10^9，因此k最大可取30。（注意打表）

最后注意ai==aj的情况，须满足数列中==ai数的个数>=2，因此map的value可以存储该数在数列中的个数。

实现代码：

#include
#include
#include

The end；

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！