题目传送门
题目大意
题目描述
在坐标线上有 n n n 个不同的点，第 i i i 个点的坐标为 x i x_i xi。选择给定点集的一个子集，使得子集中每对点之间的距离是 2 d 2^d 2d 的整数幂。需要考虑每对点，而不仅仅是相邻的点。注意，包含一个元素的任何子集都满足上述条件。在所有这些子集中，选择具有最大可能大小的子集。
换句话说，你需要选择尽可能多的点 x i 1 , x i 2 , … , x i m x_{i_1}, x_{i_2}, \dots, x_{i_m} xi1,xi2,…,xim，使得对于每一对 x i j x_{i_j} xij， x i k x_{i_k} xik，满足 ∣ x i j − x i k ∣ = 2 d |x_{i_j} - x_{i_k}| = 2^d ∣xij−xik∣=2d，其中 d d d 是某个非负整数（不必对每对点都相同）。
输入格式
第一行包含一个整数 n n n（ 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \le n \le 2 \cdot 10^5 1≤n≤2⋅105）— 点的数量。
第二行包含 n n n 个两两不同的整数 x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x1,x2,…,xn（ − 1 0 9 ≤ x i ≤ 1 0 9 -10^9 \le x_i \le 10^9 −109≤xi≤109）— 点的坐标。
输出格式
第一行输出一个整数 m m m — 满足上述条件的子集中点的最大可能数量。
第二行输出 m m m 个整数 — 选定子集中的点的坐标。
如果存在多个答案，输出其中任意一个即可。
解题思路
简化题意得：给你有 n n n 个数字的一个数列，问最多有多少个数字他们两两的差是 2 2 2 的幂次方数。
首先我们可以得出我们选择的数不超过 3 3 3 个。
为什么呢？我们都知道如果 2 i + 2 j = a k 2^i+2^j=a^k 2i+2j=ak，那么 i = j , k = 2 × i = 2 × j i=j,k=2\times i=2\times j i=j,k=2×i=2×j，我们设取出的 3 3 3 个数为 a , b , c a,b,c a,b,c，首先它们一定满足 ∣ a − b ∣ = 2 i , ∣ b − c ∣ = 2 j , ∣ a − c ∣ = 2 k |a-b|=2^i,|b-c|=2^j,|a-c|=2^k ∣a−b∣=2i,∣b−c∣=2j,∣a−c∣=2k。
∵ ∣ a − c ∣ = ∣ a − b ∣ + ∣ b − c ∣ \because |a-c|=|a-b|+|b-c| ∵∣a−c∣=∣a−b∣+∣b−c∣。
∴ k = i + j \therefore k = i + j ∴k=i+j。
因此我们可以构造这个序列，比如 a = 1 , b = 3 , c = 5 a=1,b=3,c=5 a=1,b=3,c=5。
如果我们再取一个数 d d d，那么 ∣ a − b ∣ = 2 i , ∣ b − c ∣ = 2 j , ∣ c − d ∣ = 2 p , ∣ a − d ∣ = 2 q |a-b|=2^i,|b-c|=2^j,|c-d|=2^p,|a-d|=2^q ∣a−b∣=2i,∣b−c∣=2j,∣c−d∣=2p,∣a−d∣=2q。
∵ ∣ a − d ∣ = ∣ a − b ∣ + ∣ b − c ∣ + ∣ c − d ∣ \because |a-d|=|a-b|+|b-c|+|c-d| ∵∣a−d∣=∣a−b∣+∣b−c∣+∣c−d∣。
∴ q = i + j + p \therefore q=i+j+p ∴q=i+j+p
然而 3 × 2 i ≠ 2 q 3\times 2^i \ne 2^q 3×2i=2q，这个序列既然连一部分的条件都满足不了，那么所有条件一定也不能全部满足，所以当我们取的数字数量为 4 4 4 的时候无解。
如果我们取 x ( x > 4 ) x(x>4) x(x>4) 个数字，那么包含了取 4 4 4 个数字的情况，显然无解。
所以我们取的序列长度必须小于等于 3 3 3，且经递增排序后，相邻两数之差相等。因此，我们可以先枚举整个序列中起始位置的数 y y y，再依次判断 y + 2 k , y + 2 k + 1 y+2^k,y+2^{k+1} y+2k,y+2k+1 是否在序列中出现过并进行统计即可。
CODE:
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[200010];
int n;
map<int, bool> m;
int k[200010];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (register int i = 1; i <= n; i++) {
cin >> a[i];
m[a[i]] = 1;
}
int ans = 0;
//蒟蒻赛时没有想那么多，这里枚举的是序列长度大于 1 且小于等于 3 的解
for (register int i = 1; i <= n; i++) {
for (register int j = 0; j <= 30; j++) {
int o = 1;
o <<= j;
if (m.count(a[i] + o)) { //也可以排序后二分哦
int temp = a[i] + o;
if (ans <= 2)
k[1] = a[i], k[2] = temp, ans = 2;
if (m.count(temp + o)) {
cout << 3 << endl;
cout << k[1] << ' ' << k[2] << ' ' << k[2] + o;
return 0;
}
}
}
}
if (ans == 0) { //如果找不到长度大于 1 且小于等于 3 的序列随便输出序列中的一个数即可。
cout << 1 << endl;
cout << a[1] << endl;
return 0;
}
cout << ans << endl;
for (int i = 1; i <= ans; i++)
cout << k[i] << ' ';
return 0;
}
总结
这道题目主要是序列长度小于等于 3 3 3 的地方需要一定的时间去证明，总体来说思路比较容易想到。
标签：le,cout,int,题解,整数,Points,序列,Powers,2i From： https://blog.csdn.net/2301_76224755/article/details/139743791