CF988D Points and Powers of Two

思路

首先发现选出的数最多 $3$ 个，考虑反证法。假设选出了四个数 $a,b,c,d$，并令：

$$|a - b| = 2^{x_1},|b - c| = 2^{x_2},|c - d| = 2^{x_3}$$

又因为，$|a - c|,|b - d|$ 也都是 $2$ 的次幂，那么有 $x_1 = x_2 = x_3$。于是 $|a - d| = 3 \times 2^{x_0} \neq 2^k$。

在上述过程中可以发现，相邻的数的差是相同的。

直接用 map 乱存一下即可。

Code

#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

const int N = 2e5 + 10;
int n,arr[N];
map<int,bool> vis;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

signed main(){
    n = read();
    for (re int i = 1;i <= n;i++) arr[i] = read(),vis[arr[i]] = true;
    for (re int i = 1;i <= n;i++){
        for (re int j = 0;j <= 30;j++){
            int t = (1ll << j);
            if (vis.count(arr[i] + t) && vis.count(arr[i] + 2 * t)) return printf("3\n%lld %lld %lld",arr[i],arr[i] + t,arr[i] + 2 * t),0;
        }
    }
    for (re int i = 1;i <= n;i++){
        for (re int j = 0;j <= 30;j++){
            int t = (1ll << j);
            if (vis.count(arr[i] + t)) return printf("2\n%lld %lld",arr[i],arr[i] + t),0;
        }
    }
    printf("1\n%lld",arr[1]);
    return 0;
}