Codeforces 988D Points and Powers of Two 【性质】【卡常】

这道题关键在于想到两个性质，想到就好做了。这还是我做过的第一道卡常题

1.满足题目中条件的子集，其中元素个数不能大于3

2.如果最大子集为3的话，那一定是x-2^i,  k, x+2^i的形式，我们枚举x就好了，然后i的次数是log10^9；如果最大子集是2，那就是x,x+2^i的形式，同样枚举x；如果最大子集是1，输出a[1]就行

整体复杂度是O(n*logn*log10^9)

 

#include<iostream>
#include<set>
using namespace std;

int a[200005];
set<int> m;

int main(){
    int n,size=0; cin>>n;
    int x1,x2;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        m.insert(a[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<31;j++) {
            if( m.count( a[i]+(1<<j)  ) && m.count( a[i]-(1<<j)  ) ){
                cout<<3<<endl;
                cout<<a[i]<<" "<<a[i]+(1<<j)<<" "<<a[i]-(1<<j);
                return 0;
            }
            if( m.count( a[i]+(1<<j)  ) && size==0) {
                size = 2;
                x1 = a[i];
                x2 = a[i] + (1 << j);
            }
        }
    }
    if(size==2) cout<<2<<endl<<x1<<" "<<x2;
    else cout<<1<<endl<<a[1];

    return 0;
}