D. Maximum AND - 题解

比赛与标签

比赛: Educational Codeforces Round 134 (Rated for Div. 2) 标签: bitmasks, dfs and similar, divide and conquer, greedy, sortings 难度: *1800

题目大意喵~

主人你好呀~！今天我们来解决一个超级有趣的位运算谜题，喵~

题目给了我们两个长度都是 n 的整数数组 a 和 b。我们可以任意地重新排列数组 b 中的元素，得到一个新的 b'。

接下来，我们会根据 a 和 b' 生成一个新的数组 c，规则是 c_i = a_i ⊕ b'_i（这里的 ⊕ 是按位异或 XOR 的意思哦）。

最后，我们要计算一个函数 f(a, b') 的值，它等于数组 c 中所有元素的按位与（AND）结果，也就是 c_1 & c_2 & ... & c_n。

我们的任务就是，找到一种 b 的排列方式，使得这个最终的按位与结果最大！请你告诉本喵这个最大值是多少吧，呐~

解题思路大揭秘！

看到“最大值”和“位运算”，聪明的猫娘我呀，第一个想到的就是 按位贪心 的策略！这就像搭积木一样，我们总是希望先把最高位的积木放好，因为它对整个数值的贡献是最大的，对吧？

我们的目标是让最终的 AND 结果 X 尽可能大。我们可以从二进制的最高位（比如第29位）开始，一位一位地决定 X 的这一位是 1 还是 0。

假设我们已经确定了 X 的前几位，当前得到的答案是 ans。现在我们来考虑第 k 位。我们能不能让最终结果的第 k 位也为 1 呢？

如果我们想让第 k 位为 1，那么我们期望达到的新目标值就是 candidate = ans | (1 << k)。

为了让所有 c_i 的按位与结果包含 candidate 的所有位，就必须满足对于每一个 i（从 1 到 n），都有 c_i & candidate == candidate。把 c_i 换掉，就是 (a_i ⊕ b'_i) & candidate == candidate。

这个式子看起来还是和 b 的排列有关，有点复杂呢。别急，我们来施展一点魔法，喵~

这个条件只关心 candidate 中为 1 的那些位。所以，我们可以对式子两边都用 candidate 进行 & 运算，它等价于： (a_i & candidate) ⊕ (b'_i & candidate) == candidate

哇！我们把这个等式变个形，把 (a_i & candidate) 移到右边去： (b'_i & candidate) == (a_i & candidate) ⊕ candidate

这简直是天大的发现！这个式子告诉我们：对于每一个 a_i，为了满足 candidate 这个目标，它所配对的 b'_i 必须满足一个特定的条件。具体来说，b'_i 在 candidate 掩码下的值 (b'_i & candidate) 必须等于 (a_i & candidate) ⊕ candidate。

这下问题就清晰多啦！对于 a 数组中的每一个元素 a_i，我们都计算出了它所“需要”的配对伙伴 b' 应该满足的条件，我们把这个需要的值记为 req_i = (a_i & candidate) ⊕ candidate。

现在，我们手头有一个“需求”集合 {req_1, req_2, ..., req_n}。同时，我们还有一个“供给”集合，就是我们能从 b 数组中提供的所有值，在 candidate 掩码下的结果，即 {b_1 & candidate, b_2 & candidate, ..., b_n & candidate}。

因为我们可以任意排列 b，所以只要“需求”集合和“供给”集合是完全一样的（允许有重复元素，也就是多重集相同），我们就能找到一个完美的排列 b' 来满足所有配对！

如何判断两个多重集是否相等呢？最简单的方法就是把它们都排个序，然后一个一个比较看是不是完全一样！

所以，我们的完整贪心策略就是：

初始化最终答案 ans = 0。
从高到低遍历每一个二进制位 k (从 29 到 0)。
构造一个临时的目标值 candidate = ans | (1 << k)。
根据 a 数组生成“需求”列表：req_i = (a_i & candidate) ⊕ candidate。
根据 b 数组生成“供给”列表：val_i = b_i & candidate。
将 req 和 val 两个列表排序。
如果排序后的两个列表完全相同，说明 candidate 这个目标是可以达成的！太棒了！我们就更新 ans = candidate。否则，说明我们太贪心了，第 k 位无法变成 1，ans 保持不变。
遍历完所有位后，ans 就是我们能得到的最大结果啦！

是不是感觉思路一下子就清晰了呢？喵~

代码实现喵~

下面就是把我们的思路变成代码的样子啦！本喵加了好多注释，方便主人理解哦~

cpp

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

using namespace std;

int main() {
    // 加速输入输出，让程序跑得更快，喵~
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }

        int ans = 0;
        // 预分配内存可以避免循环中重复的内存分配，是小小的优化技巧哦
        vector<int> req, val;
        req.reserve(n);
        val.reserve(n);

        // 从最高位开始贪心，喵~ (29是因为题目说 a_i, b_i < 2^30)
        for (int bit = 29; bit >= 0; bit--) {
            // 假设我们当前的答案是ans，尝试让第bit位也变成1
            // candidate 就是我们这次想尝试达成的目标值
            int candidate = ans | (1 << bit);

            // 清空上次循环用的数据
            req.clear();
            // 根据我们的推导，要达成candidate，需要 a_i 和 b'_j 配对后满足：
            // (b'_j & candidate) == (a_i & candidate) ^ candidate
            // 所以我们计算出每个 a_i "需要" 的 b'_j 的部分 (b'_j & candidate)
            for (int i = 0; i < n; i++) {
                req.push_back((a[i] & candidate) ^ candidate);
            }

            val.clear();
            // 再计算出每个 b_i "能提供" 的部分 (b_i & candidate)
            for (int i = 0; i < n; i++) {
                val.push_back(b[i] & candidate);
            }

            // 排序后看两个集合是否完全一样，就知道能不能成功配对啦！
            sort(req.begin(), req.end());
            sort(val.begin(), val.end());
            
            // 如果两个多重集相同
            if (req == val) {
                // 说明 candidate 是可以达成的，更新我们的答案！
                ans = candidate;
            }
        }

        cout << ans << '\n';
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(D * N * logN) 的说。这里的 D 是我们考虑的二进制位数，大约是30。外层循环执行 D 次。在循环内部，我们需要构建两个大小为 N 的数组，这需要 O(N) 的时间。然后对这两个数组排序，需要 O(N * logN) 的时间。所以总的时间复杂度就是 D 乘以 N*logN 啦。
空间复杂度: O(N) 的说。我们主要需要额外的空间来存储 req 和 val 这两个临时数组，它们的大小都是 N，所以空间复杂度是 O(N)。

知识点与总结

这次的解题之旅是不是很有收获呀？我们来总结一下学到了什么吧，喵！

按位贪心 (Greedy from MSB): 这是解决位运算求最值问题的“万能钥匙”之一！从高位到低位依次决策，因为高位永远比所有低位的总和更有价值。记住这个思想，以后遇到类似问题就能迎刃而解啦。
问题转化 (Problem Transformation): 最关键的一步，就是把 "是否存在一个排列 b'" 这种组合问题，通过位运算的恒等变换，转化成了 "两个导出的多重集是否相等" 这样一个更容易判断的问题。这种化繁为简的能力是成为算法高手的必备技能哦！
多重集比较 (Multiset Comparison): 我们用 排序 + 逐一比较 的方法来判断两个多重集是否相等。这是一个非常实用且常见的技巧。在C++中，如果两个 vector 排序后内容相同，直接用 == 比较就能得到我们想要的结果，非常方便！

希望本喵的讲解对你有帮助！继续加油，享受每一道题带来的挑战和乐趣吧，喵~！

D. Maximum AND - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​