C. Summarize to the Power of Two

题目链接

Codeforces Round #496 (Div. 3)--C. Summarize to the Power of Two

题解

中档题。给定一组数字,判断至少要删去多少数字可以满足其中每个数字都有对应的一个数使得相加后为2的幂次。
根据数据规模判断2的1~30次幂减去当前数得到的值是否在序列中。如果均不在则应删去这个数。

代码

#include <iostream>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
using namespace std;
int n, ans(0);
set<int>sets;
map<int, int>nums;
int b[50], inputs[120005];
int main() {
    cin >> n;
    b[0] = 1;
    for (int i = 1; i <= 30; i++) {
        b[i] = b[i - 1] * 2;
    }
    for (int i = 1; i <= n; i++) {
        cin >> inputs[i];
        sets.insert(inputs[i]);
        nums[inputs[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        bool boolean = false;
        for (int j = 0; j <= 30; j++) {
            if (sets.find(b[j] - inputs[i]) != sets.end())
            {
                if ((b[j] != inputs[i] * 2) || (b[j] == inputs[i] * 2 && nums[inputs[i]] > 1)) {
                    boolean = true;
                    break;
                }
            }
        }
        if (!boolean)
            ans++;
    }
    cout << ans;
}

标签: brute force

添加新评论