F. Lisa and the Martians - 题解

比赛与标签

比赛: Codeforces Round 888 (Div. 3) 标签: bitmasks, greedy, math, strings, trees 难度: *1800

题目大意喵~

有一位名叫 Lisa 的小可爱被火星人抓走啦！火星人给了她 n 个“火星数” a_1, a_2, ..., a_n（其实就是小于 2^k 的非负整数），然后要求 Lisa 自己也想一个火星数 x。

接下来，Lisa 需要从给定的 n 个数中选出两个不同的数 a_i 和 a_j，并计算 (a_i ⊕ x) & (a_j ⊕ x) 的值。这里的 ⊕ 是按位异或（XOR），& 是按位与（AND）。

为了能早点回家，Lisa 必须让这个计算结果尽可能地大！我们的任务就是帮助 Lisa 找到这样一组 i, j, x，使得最终的计算值最大。

简单来说，就是要在 n 个数里找俩数 a_i, a_j，再找一个 x，最大化 (a_i ⊕ x) & (a_j ⊕ x) 的值，然后输出 i, j 和 x 就可以啦，喵~

解题思路大揭秘！

初看这个问题，要同时确定 i, j, x 三个变量，感觉像是大海捞针，无从下手呀，对吧？但是不要慌，让咱带你来分析一下这个神奇的表达式 (a_i ⊕ x) & (a_j ⊕ x)，秘密就藏在里面哦！

我们知道，位运算的每一位都是独立计算的。所以，我们可以单独来看结果的每一个二进制位是 0 还是 1。

设 res = (a_i ⊕ x) & (a_j ⊕ x)。为了让 res 的第 b 位为 1，那么 (a_i ⊕ x) 和 (a_j ⊕ x) 的第 b 位都必须是 1。

我们来分情况讨论一下 a_i 和 a_j 的第 b 位（记作 a_i[b] 和 a_j[b]）：

如果 a_i[b] 和 a_j[b] 相同：
- 情况一: a_i[b] = 0 且 a_j[b] = 0。为了让 (a_i[b] ⊕ x[b]) = 1 并且 (a_j[b] ⊕ x[b]) = 1，我们只需要让 x 的第 b 位 x[b] = 1 就可以啦！这样 (0 ⊕ 1) = 1，两个条件都满足，结果的第 b 位就是 1。
- 情况二: a_i[b] = 1 且 a_j[b] = 1。同理，我们只需要让 x[b] = 0，就能得到 (1 ⊕ 0) = 1，结果的第 b 位也是 1。
小结一下：只要 a_i 和 a_j 在某一位上相同，我们总能找到一个合适的 x 的位，使得结果的这一位变成 1！
如果 a_i[b] 和 a_j[b] 不同：
- 比如说 a_i[b] = 0 而 a_j[b] = 1。
- 我们需要 (0 ⊕ x[b]) = 1，这意味着 x[b] 必须是 1。
- 同时我们又需要 (1 ⊕ x[b]) = 1，这意味着 x[b] 必须是 0。
- x[b] 不可能同时是 0 和 1 呀！这是一个矛盾，喵~！所以，只要 a_i 和 a_j 在某一位上不同，无论 x 的这一位是什么，结果的这一位都永远是 0。

核心洞察来啦！ 通过上面的分析，我们发现，对于一对固定的 (a_i, a_j)，能得到的最大结果 res 的二进制表示是这样的：

如果 a_i 和 a_j 的第 b 位相同，res 的第 b 位就是 1。
如果 a_i 和 a_j 的第 b 位不同，res 的第 b 位就是 0。

这不就是 ~(a_i ⊕ a_j) 吗？（~ 是按位取反）。也就是说，对于一对 (a_i, a_j)，我们能获得的最大值完全由它们自己决定，和 x 无关！x 只是一个工具人，用来实现这个最大值。

我们的目标是最大化 res，也就是最大化 ~(a_i ⊕ a_j)。要让一个数的按位取反结果最大，这个数本身就得最小！所以，问题就神奇地转化为了：

在 n 个数中，找到一对 (a_i, a_j)，使得它们的异或和 a_i ⊕ a_j 最小！

这个问题就经典多啦！想找到一个数组里的最小异或对，有一个非常高效的技巧：

先将数组排序！
遍历排序后的数组，最小的异或值一定出现在相邻的两个元素之间！

为什么呢？可以这样想，如果最小异或对 (a, c) 在排序后不相邻，中间隔了一个 b（即 a < b < c），那么 min(a⊕b, b⊕c) 一定会小于 a⊕c。所以最小异或对一定是邻居~

最终的算法步骤：

把输入的 n 个数和它们的原始下标（从1开始哦）存成一个 pair 或者结构体数组。
对这个数组按照数值大小进行排序。
遍历排序后的数组，计算每一对相邻元素 v[i] 和 v[i+1] 的异或值，找到那个异或值最小的相邻对。记下它们的数值 val1, val2 和原始下标 idx1, idx2。
我们已经找到了最优的 (a_i, a_j)，现在需要构造对应的 x。根据我们最初的分析：
- 在 val1 和 val2 相同的位上，我们要取反。比如 val1 和 val2 在某位都是 0，x 在这位就得是 1。
- 在 val1 和 val2 不同的位上，x 可以随意取，取 0 就好。
- 这合起来就是：x 在某位是 1，当且仅当 val1 和 val2 在该位都是 0。这不就是 (~val1) & (~val2) 嘛！
最后，别忘了 x 也是个火星数，要小于 2^k。所以要用一个 (1LL << k) - 1 的掩码来限制一下范围。
输出我们找到的 idx1, idx2 和计算出的 x，大功告成，喵~！

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

// 解决单个测试用例的函数喵~
void solve() {
    int n;
    int k;
    std::cin >> n >> k;
    
    // 用一个 pair 数组来存储数值和它原本的下标
    std::vector<std::pair<int, int>> v(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> v[i].first;
        v[i].second = i + 1; // 题目要求输出1-based的下标
    }

    // 按照数值进行排序，这是高效找到最小异或对的关键一步！
    std::sort(v.begin(), v.end());

    // 寻找排序后数组中，异或和最小的相邻对
    // 这个相邻对就是全局的最小异或对哦！
    int min_xor_val = -1; // 用-1表示还没找到
    int best_i = -1;      // 记录最优对的第一个元素的索引

    for (int i = 0; i < n - 1; ++i) {
        int current_xor = v[i].first ^ v[i+1].first;
        if (best_i == -1 || current_xor < min_xor_val) {
            min_xor_val = current_xor;
            best_i = i;
        }
    }

    // 找到了最优的那一对！就是 v[best_i] 和 v[best_i+1]
    int p1_idx = v[best_i].second;
    int p2_idx = v[best_i+1].second;
    int val1 = v[best_i].first;
    int val2 = v[best_i+1].first;

    // 现在来构造最优的 x
    // 为了最大化 (val1 ⊕ x) & (val2 ⊕ x)，我们根据 val1 和 val2 的位来决定 x 的位
    // 如果 val1 和 val2 在某一位上相同，我们可以让结果的这一位为 1。
    // 如果它们在某一位上不同，结果的这一位永远是 0。
    // 一个能实现最大值的 x 的选择是：当且仅当 val1 和 val2 的某一位都是0时，x 的对应位才为1。
    // 这可以用公式 x = (~val1) & (~val2) 来计算。
    long long k_mask = (1LL << k) - 1; // 创建一个 k 位的掩码，确保 x 是合法的火星数
    int x = (~val1) & (~val2) & k_mask;

    std::cout << p1_idx << " " << p2_idx << " " << x << "\n";
}

int main() {
    // 加速一下输入输出，跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析的说

时间复杂度: O(N log N) 的说。算法的主要开销在于对 n 个数进行排序，这需要 O(N log N) 的时间。之后遍历一遍数组寻找最小异或对需要 O(N) 的时间。所以总的时间复杂度由排序决定，就是 O(N log N) 啦。
空间复杂度: O(N) 的说。我们需要一个额外的 std::vector<std::pair<int, int>> 来存储 n 个数和它们的原始下标，所以空间复杂度是 O(N)。

知识点与总结

这道题真的非常巧妙，把一个看起来很复杂的问题，通过位运算的分析，变成了一个我们熟悉的问题。真是太有意思了，喵~

核心思想：问题转化 最重要的一步就是把最大化 (a_i ⊕ x) & (a_j ⊕ x) 的问题，转化为了最小化 a_i ⊕ a_j 的问题。这种转化思维在算法竞赛中非常重要，能让你拨开迷雾，看到问题的本质！
关键算法：寻找最小异或对 “排序后，最小异或对必在相邻元素中” 这个结论是一个非常有用的技巧！以后再遇到类似求最小/最大异或对的问题，一定要先想到排序哦！
位运算技巧 (Bitmask) 对 &（与）和 ⊕（异或）的深刻理解是解题的基础。特别是如何通过构造 x 来控制 a ⊕ x 的每一位，以及 x = (~val1) & (~val2) & k_mask 这个构造公式，都体现了位运算的魅力。
注意事项 在排序前，千万别忘了保存元素的原始下标！不然找到最优的数值对了，却不知道它们原来在第几个位置，那就白费功夫啦。使用 std::pair 是一个非常优雅的解决方案。

希望这篇题解能帮助到大家！你看，只要我们静下心来，一点点分析，问题就迎刃而解了对吧？继续加油，期待和大家在下一道题再会，喵~！

F. Lisa and the Martians - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​