Problem - 988D - D. Points and Powers of Two(思维)

D. Points and Powers of Two

题目大意:给定若干个数$x_i$,找出其中一个子集,满足子集中任意两个数的差值的绝对值都是$2^x$,求最大数量的子集.

解题思路:简单分析一下,一个符合条件的子集最多只能有$3$个元素,$a_i,a_i+2^j,a_i+2^{j+1}$,这种情况下,才能保证任意两个元素差值都是$2^x$,然后直接枚举即可.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int N = 2e5+5;
ll a[N];
ll pre[50];
int main(){
    syncfalse#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifpre[0]=1;for (int i = 1; i <= 31; ++i)pre[i]=pre[i-1]*2;int n;cin>>n;set<int>s;for (int i = 1; i <= n; ++i){
    cin>>a[i];s.insert(a[i]);}vector<int>ans;vector<int>tem;int cnt = 0, num = 1;for (int i = 1; i <= n; ++i){
    for (int j = 0; j < 31; ++j){
    tem.push_back(a[i]);if (s.count(a[i]+pre[j])){
    num++;tem.push_back(a[i]+pre[j]);}if (s.count(a[i]+pre[j+1])){
    num++;tem.push_back(a[i]+pre[j+1]);}if (num>cnt){
    ans=tem;cnt=num;}tem.clear();num=1;}}cout << cnt << "\n";for (auto x : ans)cout << x << " ";return 0;
}