排序 + 二分 + 枚举
时间复杂度大概是 $ O(32 * nlogn) $
比较极限,跑出来最快是 9246ms,开o2的话最快 3325ms.
首先我们通过枚举子集可以知道子集的最大元素数量是 3 。( 比赛时没推出这个结论直接写,结果直接Wa了)
通过分析子集,可以知道‘子集内的元素满足任意两元素之差的绝对值都是 2 的整数幂’ 一定是个差值为 2 的整数次幂 的等差数列。
那么就可以直接枚举了
大概枚举思路:枚举 2 的次幂,看不断二分查数列下一项最终得到的等差数列长度 cnt 是否比 ans 大,如果cnt大就取cnt,否则跳过
c++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 2e5 + 10;
int two[40],res[2][maxn],a[maxn],ans;
bool used[maxn][40];
int main(){
int n;
scanf("%d",&n);
for (int i = 0 ; i < 32 ; ++i)
two[i] = 1 << i; //预处理2 的 i 次幂
for (int i = 1 ; i <= n ; ++i)
scanf("%d",a + i);
sort(a + 1,a + n + 1); // 先排序,方便后面二分
int cnt = 0,id,last,p = 0; // cnt 计数,id 存二分得到的下标,last存上一个查询的值的下标,p 为滚动数组的下标
n = unique(a + 1,a + n + 1) - a - 1; //因为子集元素互异,所以同样的值结果相同,因此可以先去重。
ans = 1;
res[p ^ 1][ans] = a[ans]; //子集至少有一个元素
for (int i = 1 ; i <= n && ans < 3; ++i){
for (int j = 0 ; j < 32 ; ++j){
if (used[i][j]) //空间换时间,用来判断当前a[i]有没有试过j次幂。如果有可以跳过
continue ;
id = lower_bound(a + i + 1,a + n + 1,a[i] + two[j] * ans) - a;
if (id == n + 1 || a[id] != a[i] + two[j] * ans) //用来判断是否可能比最优解好,不好则跳过
continue ;
cnt = 0;
res[p][++cnt] = a[i];
id = i;
while (id < n && cnt < 3){
last = id;
id = lower_bound(a + id + 1,a + n + 1,a[id] + two[j]) - a; //二分查等差数列下一项
if (id == n + 1 || a[id] - a[last] != two[j])
break;
res[p][++cnt] = a[id];
used[id][j] = 1;
}
if (cnt > ans) //如果比最优解好,就选择当前结果。
ans = cnt,p ^= 1;
}
}
p ^= 1; //滚动数组,滚回答案数组
printf("%d\n",ans);
for (int i = 1 ; i <= ans ; ++i)
printf("%d ",res[p][i]);
return 0;
}