题目描述
给定一个包含 n 个元素的整数集合。
集合中的元素两两不同。
请你找到一个该集合的最大子集,要求子集内的元素满足任意两元素之差的绝对值都是 2 的整数幂。
注意,只包含 1 个元素的子集一定满足条件。
输入样例1:
6
3 5 4 7 10 12
输出样例1:
3
7 3 5
输入样例2:
5
-1 2 5 8 11
输出样例2:
1
8
分析
$设有三个数A,B,C$
$满足A < B < C$
$若A + 2^x = B$
$B + 2^y = C$
$A + 2^z = C$
$那么A + 2^x + 2^y = C$
$即2^x + 2^y = 2^z$
$满足 x = y , z = x + 1$
$B = A + 2^x$
$C = B + 2^x$
$C = A + 2^{x+1}$
$设有四个数A , B, C, D$
$A < B < C < D$
$若能成立,一定满足:$
$$B = A + 2^x$$
$$C = B + 2^x$$
$$C = A + 2^{x+1}$$
$$D = A + 2^{x+2}$$
$$D = C + 2^{x+1}$$
$又因为$
$$D = C + 2^{x+1} = B + 2^x + 2^{x+1}$$
$不满足性质,即取出的数最多只能有3个$
$Code$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010, C = 32, M = 19999997, inf = 0x3f3f3f3f;
int h[M];
int g[N][C], a[N];
int find(int x) // 手写hash
{
int t = (x % M + M) % M;
while (h[t] != inf && h[t] != x)
if (++ t == M)
t = 0;
return t;
}
int main()
{
memset(h, 0x3f, sizeof h);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
h[find(a[i])] = a[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < C; j ++ )
{
ll k = (ll)a[i] + (1 << j);
if (k > 1e9)continue;
if (h[find(k)] == inf)continue;
g[i][j] = 1;
}
int res = 1, ii, jj;
for (int i = 0; i < C - 1; i ++ )//枚举x
{
for (int j = 1; j <= n; j ++ )
{
int m = g[j][i] + g[j][i + 1] + 1;
if (m > res)
{
res = m;
ii = i, jj = j;
}
if (res == 3)break;
}
if (res == 3)break;
}
printf("%d\n", res);
if (res == 1)cout << a[1];
else
{
printf("%d ", a[jj]);
if (g[jj][ii])printf("%d ", a[jj] + (1 << ii));
if (g[jj][ii + 1])printf("%d ", a[jj] + (1 << ii + 1));
}
return 0;
}
哈希用unordered_set为什么会超时呢?count的平均复杂度不是O(1)吗?
unordered_set虽然是 $O(1)$,但是比手写哈希慢,会被卡常
%%%