G. Orray - 题解

比赛与标签

比赛: Codeforces Round 827 (Div. 4) 标签: bitmasks, brute force, greedy, math, sortings 难度: *1500

题目大意喵~

主人你好呀~ 这道题是这样子的喵：

我们拿到一个由 n 个非负整数组成的数组 a。然后呢，我们要定义一个叫做“前缀或”的数组 b。b 数组的第 i 个元素 b_i 是 a 数组从第 1 个到第 i 个元素进行“按位或”（Bitwise OR）运算的结果，也就是 b_i = a_1 | a_2 | ... | a_i 啦。

我们的任务是，重新排列数组 a 里的元素，使得最终得到的“前缀或”数组 b 在字典序上是最大的！最后，把这个重新排列好的 a 数组打印出来就可以啦，喵~

简单来说，就是想让 b 数组的第一个元素 b_1 尽可能大，如果 b_1 相同，就让 b_2 尽可能大，以此类推，直到最后一个元素。

贪心思路大揭秘！

这道题要求字典序最大，一看到这个，我们就要本能地想到贪心策略啦，喵！字典序比较，最重要的就是排在最前面的元素。

1. 第一步，让 b_1 最大化！b_1 就是我们排好序的 a 数组的第一个元素 a'_1。为了让 b_1 最大，我们是不是应该在原数组 a 中选一个数作为 a'_1，使得 b_1 的值最大呢？但是，只考虑数值最大的数可能不是最优解哦。比如 {3, 5}，如果我们选 5，b 数组是 {5, 7}；如果选 3，b 数组是 {3, 7}。{5, 7} 确实更大。但我们的目标是让整个 b 数组字典序最大。

2. 推广到每一步，让 b_k 最大化！ 让我们来系统地思考一下，喵~

   • 当我们决定第一个元素 a'_1 时，b_1 就等于 a'_1。为了让 b_1 尽可能大，我们应该选择一个 a_i，使得 0 | a_i 最大。这其实就是选择 a_i 本身最大的那个嘛？不完全是哦，更准确地说是选择能让当前前缀或值最大的那个！
   • 假设我们已经选好了前 k-1 个元素，得到了一个前缀或值 current_or = a'_1 | a'_2 | ... | a'_{k-1}。现在我们要从剩下的元素里选第 k 个元素 a'_k。新的前缀或值将是 b_k = current_or | a'_k。为了让 b_k 尽可能大，我们理所当然应该在所有还没用过的元素中，找到那个能让 current_or | a'_k 最大的元素，然后把它作为我们的 a'_k！

   这个思路是不是非常直接，非常符合直觉呢？喵~ 这就是我们的核心贪心策略：在每一步，都选择一个能使当前前缀或值变得最大的未使用过的元素。

举个例子吧！a = {1, 2, 4, 8}

• 第1步: current_or = 0。遍历所有数：0|1=1, 0|2=2, 0|4=4, 0|8=8。8 最大！我们选 8。
  • 排列好的数组 p = {8}。
  • current_or 更新为 8。
• 第2步: current_or = 8。在剩下的 {1, 2, 4} 中选：8|1=9, 8|2=10, 8|4=12。12 最大！我们选 4。
  • 排列好的数组 p = {8, 4}。
  • current_or 更新为 12。
• 第3步: current_or = 12。在剩下的 {1, 2} 中选：12|1=13, 12|2=14。14 最大！我们选 2。
  • 排列好的数组 p = {8, 4, 2}。
  • current_or 更新为 14。
• 第4步: 只剩下 {1} 了，选它！
  • 排列好的数组 p = {8, 4, 2, 1}。
  • current_or 更新为 15。

最终得到的排列就是 8 4 2 1，和样例一样呢！说明我们的贪心思路是正确的，耶！

代码实现与优化喵

但是，如果每次都遍历所有 n 个数，一共要选 n 次，那复杂度不就是 O(n²) 了吗？对于 n 高达 2 * 10^5 的数据，这肯定会超时的说！

这里有一个超级棒的优化技巧，主人请看喵~ 一个 int 类型的非负整数，最多也就 30-31 个二进制位有效。我们的 current_or 值是不断增长的（因为 x | y >= x）。它要想严格变大，就必须在某次或运算中，新加入的数至少贡献了一个 current_or 原本没有的 1。 由于总共只有大约 30 个二进制位，所以 current_or 值最多只能严格增大 30 次左右。之后，它就会达到一个饱和状态——也就是数组中所有元素的按位或总和。一旦达到这个状态，后面再或上任何一个数组里的数，current_or 的值都不会再变了！

所以，我们根本不需要贪心地选 n 次！我们只需要贪心地选 min(n, 31) 次就足够了。31 是一个安全的上界（因为 2^30 > 10^9）。在这 31 次选择之后，current_or 已经饱和，剩下的元素无论以什么顺序放进去，都不会改变后续的 b_k 的值了。所以把它们直接追加到末尾就好啦！

这样一来，复杂度就从 O(n²) 降到 O(min(n, 31) * n) 了，完全可以通过！

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 快速 I/O 设置，让程序跑得更快喵~
void setup_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int& x : a) {
        std::cin >> x;
    }

    // p 是我们最终要输出的排列好的数组
    std::vector<int> p;
    p.reserve(n);
    // used 数组用来标记哪些元素已经被选走了
    std::vector<bool> used(n, false);
    // current_or 记录当前的前缀或值
    int current_or = 0;

    // 这里就是那个聪明的优化啦！
    // 贪心选择的次数是有限的。最多经过约30次选择，每次选择都至少贡献一个新的二进制位，
    // current_or 就会饱和，无法再增大了。
    // 所以循环上限 min(n, 31) 是一个安全且高效的选择。
    for (int k = 0; k < std::min(n, 31); ++k) {
        int best_idx = -1;
        int max_or_val = current_or;

        // 在所有未使用的元素中，找到那个能让当前前缀或值变得最大的元素
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                if ((current_or | a[i]) > max_or_val) {
                    max_or_val = current_or | a[i];
                    best_idx = i;
                }
            }
        }

        // 如果找不到任何元素能让 current_or 增大了，说明已经饱和，可以提前结束贪心选择
        if (best_idx == -1) {
            break;
        }

        // 把找到的最佳元素加入 p 数组
        p.push_back(a[best_idx]);
        // 标记为已使用
        used[best_idx] = true;
        // 更新 current_or
        current_or = max_or_val;
    }

    // 把剩下所有没用过的元素追加到 p 数组的末尾
    // 它们的顺序已经不影响后续的前缀或值了
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            p.push_back(a[i]);
        }
    }

    // 美美地输出答案~
    for (int i = 0; i < n; ++i) {
        std::cout << p[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    setup_io();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

• 时间复杂度: O(min(n, K) * n) 的说。其中 K 是整数的二进制位数（这里我们取31）。外层循环最多执行 K 次，内层循环每次都遍历 n 个元素。所以是 K * n 的级别。当 n 很小时，复杂度是 O(n^2)，但由于 n 的总和限制，这个复杂度是完全没问题的。
• 空间复杂度: O(n) 的说。我们用了 p 数组和 used 数组来存储结果和使用状态，都需要 O(n) 的空间。

知识点与总结

这道题真是个很好的例子，结合了贪心和位运算的智慧呢，喵~

1. 贪心算法 (Greedy Algorithm): 解决这道题的核心思想。当要求字典序最大/最小时，通常可以尝试从前往后，在每一步都做出当前看起来最优的选择。
2. 按位或 (Bitwise OR): 理解 | 运算的性质是关键。特别是 x | y >= x 这个性质，它保证了前缀或数组是单调不减的。
3. 位运算优化: 这是本题的点睛之笔！通过分析位运算的特性（一个数只有有限个二进制位），我们发现贪心过程很快就会收敛（current_or 值饱和），从而将一个看似 O(n²) 的暴力贪心优化到了近乎线性的 O(K*n) 复杂度。这个技巧在处理与位运算相关的题目时非常有用哦！

希望我的讲解对主人有帮助呐！下次遇到类似的题目，也要像猫娘一样，敏锐地发现其中的奥秘哦！加油，喵~！