题目链接

题解

所有的2的整数幂: 1, 2, 4, 8, 16

• 任意两个, 都不可以共存. 因为任意两个的和, 都不是2的整数幂
  因此, 所有数, 一定是相同的
• 相同的数, 最多有2个; 因为 任意3个数 的和, 也不是2的整数幂
  因此, 最多3个数.

即, 选出2 / 3个数a < b < c, 使得他们的差, 相同, 而且是2的整数幂
即, a, a + d, a + d*2 (d 是 1/ 2/ 4/ 8/ 16/ ...)

---

很容易想到一种算法:

int n;
scanf("%d", &n);
unordered_set< Ll_> sett;
FOR_( i, 0, n-1, 1){
    scanf("%lld", &A[ i]);
    sett.insert( A[ i]);
}
vector< Ll_> ans;
//> 3
FOR_( i, 0, n-1, 1){
    FOR_( bit, 0, 31, 1){
        Ll_ nex = A[ i] + ( 1LL << bit);
        Ll_ nexx = A[ i] + ( ( 1LL << bit) << 1);
        //--
        if( sett.find( nex) != sett.end()){
            ans = { A[ i], nex};
            //--
            if( sett.find( nexx) != sett.end()){
                printf("3\n%lld %lld %lld", A[ i], nex, nexx);
                return;
            }
        }
    }
}
//> 2
if( false == ans.empty()){
    printf("2\n%lld %lld", ans[ 0], ans[ 1]);
    return;
}
//> 1
printf("1\n%lld", A[ 0]);
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

但他是超时的…
其时间是: 2e5 * 32 * (ln2e5 + ln2e5) = 2e8

---

优化一
由于我们找的是: a, a+d, a+2*d, 这三个数, 他是单调的
在a时, 只会找比他大的数.

因此, (将数组排序后), 边查询 边插入

unordered_set< Ll_> sett;
FOR_( i, 0, n-1, 1){
    scanf("%lld", &A[ i]);
}
sort( A, A + n); //< 排序
vector< Ll_> ans;
//> 3
FOR_RE_( i, n-1, 0, 1){ //< 从大到小枚举
    FOR_( bit, 0, 31, 1){
        Ll_ nex = A[ i] + ( 1LL << bit);
        Ll_ nexx = A[ i] + ( ( 1LL << bit) << 1);
        //--
        if( sett.find( nex) != sett.end()){
            ans = { A[ i], nex};
            //--
            if( sett.find( nexx) != sett.end()){
                printf("3\n%lld %lld %lld", A[ i], nex, nexx);
                return;
            }
        }
    }
    sett.insert( A[ i]); //< 边查询 边插入
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间是: 2e5 * 32 * C, 这个C是多少 我也不知道…
反正是 刚刚好可以AC.

其实, 这个优化, 并不很强烈. 只是刚刚碰巧AC了.

这个算法的核心操作, 在于set的 插入和查询. 而 set, map, 他们的常数, 都是很大的!!
应该从优化set去入手!

---

优化二
我们发现, 这道题的核心操作, 就是insert 和 find, 插入和查询
这不就是 哈希的专长 呀!

假如上面的优化一时间是: T

整数的哈希, 这里可以使用 (开放寻址法 T/5) (离散化 T/2)

因此, 边查询, 边插入 只是个小优化;
即使 一开始把所有数都插入, 然后去统一查询, 用哈希表, 也是T/5
当然, 边插入边查询, 更好!

还有一点, -1e10, 1e10, 其差距是: 2e10, 小于其的最大2幂是: 2e30
2e32 = 4e10 + c, 2e31 = 2e10 + c, 2e30 = 1e10 + c

因此, 对于1e10 + (2e30), 也不会超int;
所以, 全程可以直接使用int, 不需要用LL

FOR_( i, 0, n-1, 1){
    scanf("%d", &A[ i]);
    Insert( A[ i]); //< 哈希插入
}
vector< int> ans;
//> 3
FOR_( i, 0, n-1, 1){ //< 不需要: 对A排序, 然后边插入边查询
    FOR_( bit, 0, 30, 1){
        int nex = A[ i] + ( 1 << bit);
        int nexx = A[ i] + ( ( 1 << bit) << 1);
        //--
        if( Find( nex)){ //< 哈希查询
            ans = { A[ i], nex};
            //--
            if( Find( nexx)){
                printf("3\n%d %d %d", A[ i], nex, nexx);
                return;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21