D. Points and Powers of Two - 题解
比赛与标签
比赛: Codeforces Round 486 (Div. 3) 标签: brute force, math 难度: *1800
题目大意喵~
主人你好呀~！是小猫娘我哦！今天我们来分析一道非常有趣的题目，喵~
题目是这样子的：在一条数轴上，我们有 n 个坐标各不相同的点。我们需要从这些点中选出一个子集，这个子集要满足一个奇妙的条件：子集中任意两个点的距离都必须是2的非负整数次幂（比如 1, 2, 4, 8, ...）。我们的目标是找到满足这个条件的、包含点数最多的子集，并把它打印出来。
简单来说，就是找一个最大的点集，使得里面任意两点 a 和 b 的距离 |a - b| 都等于 2^d（不同的点对，d 可以不同）。
解题思路，来一起推理吧！
这道题看起来有点吓人呐，n 最大有 20 万，如果暴力枚举所有子集肯定是不行的说。但是只要我们静下心来分析，就会发现一个超级重要的突破口哦！
我们来分析一下，满足条件的子集最大能有多大呢？
大小为 1 的子集:
{a}一个点自己跟自己玩，当然满足条件啦，所以答案至少是1喵。大小为 2 的子集:
{a, b}两个点的话，只要它们的距离|a - b|是2的幂次方就可以啦，比如{3, 5}，距离是2，也就是2^1。大小为 3 的子集:
{a, b, c}这可是最关键的部分！我们来仔细研究一下，喵~ 为了方便，我们假设a < b < c。那么，b-a,c-b,c-a这三个距离都必须是2的幂。 我们设b - a = 2^k并且c - b = 2^m。 那么c - a = (c - b) + (b - a) = 2^m + 2^k。 现在问题来了：两个2的幂相加，什么时候结果还是2的幂呢？ 我们来试试看：- 如果
k = m，那么2^k + 2^k = 2 * 2^k = 2^(k+1)。Bingo！这是一个2的幂！ - 如果
k < m，那么2^k + 2^m = 2^k * (1 + 2^(m-k))。因为m-k > 0，所以2^(m-k)是个偶数，1 + 2^(m-k)就是个大于1的奇数。一个大于1的奇数不可能是2的幂！ 所以呀，我们得出了一个惊人的结论：要让2^k + 2^m成为2的幂，当且仅当k = m！
这意味着
b - a必须等于c - b！也就是说，b必须是a和c的中点！ 所以，一个大小为3的合法子集，必定是{p - d, p, p + d}这样的形式，其中d是2的幂。 我们来验证一下：|p - (p - d)| = d = 2^k(OK!)|(p + d) - p| = d = 2^k(OK!)|(p + d) - (p - d)| = 2d = 2 * 2^k = 2^(k+1)(OK!) 完美！所有距离都是2的幂。比如例题中的{3, 5, 7}，就是{5 - 2^1, 5, 5 + 2^1}。
- 如果
大小为 4 的子集:
{a, b, c, d}那...四个点呢？还能更多吗？ 我们假设a < b < c < d。 根据上面的结论，子集{a, b, c}必须是{b - 2^k, b, b + 2^k}的形式。所以a = b - 2^k,c = b + 2^k。 同理，子集{b, c, d}也必须满足条件，所以它们也得是{c - 2^m, c, c + 2^m}的形式。所以b = c - 2^m,d = c + 2^m。 联立一下：b = (b + 2^k) - 2^m，可以得到2^k = 2^m，所以k = m。 那么这四个点就是：a = b - 2^k,b,c = b + 2^k,d = c + 2^k = (b + 2^k) + 2^k = b + 2 * 2^k = b + 2^(k+1)。 这个集合是{b - 2^k, b, b + 2^k, b + 2^(k+1)}。 让我们来检查一下a和d的距离：|d - a| = |(b + 2^(k+1)) - (b - 2^k)| = 2^(k+1) + 2^k = 2 * 2^k + 2^k = 3 * 2^k。 呜喵！3 * 2^k里面有个讨厌的3，它绝对不是2的幂！所以，大小为4的子集是不可能存在的！
最终策略
所以，答案的最大可能就是 3！
这下问题就变得超级简单了，我们的策略就很清晰啦：
- 优先找大小为3的子集。遍历每一个输入的点
p，把它当作中间点。然后遍历所有可能的2的幂d = 2^k，检查p - d和p + d是否都在输入的点集中。只要找到一组，就是我们的答案！ - 如果找不到大小为3的，我们再找大小为2的子集。同样，遍历每个点
p，检查p + d是否存在。找到一个就可以啦。 - 如果连大小为2的都找不到，那说明任意两点距离都不是2的幂，答案就只能是大小为1的子集了。随便输出一个点就好。
为了快速判断一个点是否存在，我们先把所有点都放进一个哈希集合（C++里的 std::unordered_set）里，这样查询起来平均就是O(1)的啦，超级快！
代码实现，Nya!
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
void solve() {
int n;
std::cin >> n;
std::vector<long long> x(n);
// 使用哈希集合来快速查找一个点是否存在，喵~
std::unordered_set<long long> s;
for (int i = 0; i < n; ++i) {
std::cin >> x[i];
s.insert(x[i]);
}
// 优先级最高：寻找大小为3的集合。这是我们能找到的最大的集合了！
for (long long p : x) {
// 遍历所有可能的2的幂，d从0到31就足够覆盖所有情况了
// 2^31 > 2*10^9，比题目中任意两点的最大距离都大
for (int d = 0; d <= 31; ++d) {
long long pow2 = 1LL << d; // 计算 2^d
// 检查 p-pow2 和 p+pow2 是否都存在于原始点集中
if (s.count(p - pow2) && s.count(p + pow2)) {
// 找到了！直接输出然后结束程序，喵！
std::cout << 3 << "\n";
std::cout << p - pow2 << " " << p << " " << p + pow2 << "\n";
return;
}
}
}
// 如果没找到大小为3的，那就退而求其次，找大小为2的
for (long long p : x) {
for (int d = 0; d <= 31; ++d) {
long long pow2 = 1LL << d;
// 检查 p+pow2 是否存在
if (s.count(p + pow2)) {
// 找到了！这是当前能找到的最好的答案
std::cout << 2 << "\n";
std::cout << p << " " << p + pow2 << "\n";
return;
}
}
}
// 如果大小为2和3的都没找到，那答案肯定是1了
// 随便输出一个点就行
std::cout << 1 << "\n";
std::cout << x[0] << "\n";
}
int main() {
// 加速输入输出，是个好习惯哦
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
solve();
return 0;
}复杂度分析
时间复杂度: O(N * log(MAX_VAL)) 的说。 我们首先需要 O(N) 的时间把所有点读入并存入哈希集合。然后，我们最多会遍历
N个点，对于每个点，我们再遍历大约32个2的幂（log(MAX_VAL)，其中MAX_VAL是坐标的最大差值）。每次查询哈希集合是 O(1) 的。所以总的时间复杂度是 O(N * log(MAX_VAL))。这个速度对于N = 2*10^5来说是绰绰有余的！空间复杂度: O(N) 的说。 我们主要用了一个哈希集合
s和一个向量x来存储输入的N个点，所以空间复杂度是 O(N)。
知识点与总结
这道题最核心的地方就是通过数学推导，将问题的规模大大简化了呢！
- 数学洞察力: 证明满足条件的集合大小最大为3，是解决本题的关键。这一下就把一个看起来很复杂的组合问题，变成了一个简单的、有固定上限的搜索问题。
- 贪心策略: 我们的解法其实是一种贪心。因为我们知道最好的答案是3，所以我们优先寻找大小为3的解。如果找不到，再寻找次好的解（大小为2），以此类推。这种从最优解开始尝试的思路在很多问题中都很有用。
- 哈希集合的应用:
std::unordered_set是处理这类“判断元素是否存在”问题的神器！它能提供平均 O(1) 的查询效率，避免了在数组或排序向量中进行 O(N) 或 O(logN) 的查找，大大提升了算法性能。
希望这篇题解能帮到主人哦！下次遇到难题也不要怕，静下心来仔细分析，总能找到线索的！加油喵~！