AcWing 4505. 最大子集

• 假设集合内A$2^x$,$2^y$,$2^z$，那么我们可以得到$2^x+2^y=2^k$，也就是$1+2^{y-x}=2^{k-x}$，除了1另外两个都只可能为1或者偶数，如果两个都是偶数就不成立了，因此，$y=x$，也就是说集合中任意两个连续的数的差值都是一样的（等差数列）都是$2^x$，这样的话A和D之间的差值就是$3\ast 2^x$，必然就不是一个2的整数幂，就不对了，因此，集合中如果包含大于等于4个数，必然出现矛盾
• 我们要多次快速查找原序列中是否有某个元素，且原序列本身都不重复，因此我们用一个set来存入原序列
• 注意这里如果用这种方式来写必须加上前两行开启O2优化

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
#define one first
#define two second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
const int N = 2e5 + 10;

int n;
int a[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    unordered_set<int> se(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j < 31; ++ j) {
            if (se.count(a[i] - (1 << j)) && se.count(a[i] + (1 << j))) {
                cout << 3 << endl;
                cout << a[i] - (1 << j) << ' ' << a[i] << ' ' << a[i] + (1 << j) << endl;
                return 0;
            }
        }
    }
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j < 31; ++ j) {
            if (se.count(a[i] - (1 << j))) {
                cout << 2 << endl;
                cout << a[i] << ' ' << a[i] - (1 << j);
                return 0;
            }
        }
    }
    cout << 1 << endl << a[1];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

• 因为用unorderd_set（常数很大）也是会tle的，因此我们手写哈希表
• 哈希表M一般是数据范围的2～3倍（下限），（由于数据范围空间足够（只有2e5）这里取十倍，）且为质数（质数是因为防止哈希碰撞 就是防止太多数取余以后相等）
• 由于这里数值有$-1e9$，可能是负数，因此给哈希表初始化就不初始化成-1，可以初始化成0x3f3f3f3f（大于1e9，且0x3f+0x3f也不超过int范围）
• 哈希表不要忘了赋值
• 哈希表可以节省三倍时间

#include 
#include 
#include 
using namespace std;
const int N = 2e5 + 10, M = 1999997, inf = 0x3f3f3f3f;

int n;
int a[N], h[M];

int find(int x) {
    int t = (x % M + M) % M;
    while (h[t] != inf && h[t] != x) {
        if ( ++ t == M) {
            t = 0;
        }
    }
    return t;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    memset(h, 0x3f, sizeof h);
    int res[4], s[4];
    int rt = 0, st = 0;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j < 31; ++ j) {
            int d = 1 << j;
            s[1] = a[i], st = 1;
            for (int k = 1; k <= 2; ++ k) {
                int now = a[i] - k * d;
                if (h[find(now)] == inf) break;
                s[ ++ st] = now;
            }
            if (rt < st) {
                rt = st;
                memcpy(res, s, sizeof s);
                if (rt == 3) break;
            }
        }
        if (rt == 3) break;
        h[find(a[i])] = a[i];
    }
    cout << rt << endl;
    for (int i = 1; i <= rt; ++ i) cout << res[i] << ' ';
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49