Moe's CF Life

Appearance

E. Compatible Numbers - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 112 (Div. 2) 标签: bitmasks, brute force, dfs and similar, dp 难度: *2200

题目大意喵~ 🐾 ​

哈喵~！各位算法大师们好呀！今天我们来看一道非常有趣的位运算题目哦！

题目是这样定义的说：如果两个整数 x 和 y 的按位与（Bitwise AND）结果为 0（也就是 x & y == 0），那么它们就是“兼容”的。

现在，我们拿到一个整数数组 a，包含 n 个元素。我们的任务是，对于数组中的每一个元素 a_i，都需要找到一个存在于数组 a 中的数字 a_j，使得 a_i 和 a_j 是兼容的。如果能找到，就输出任意一个满足条件的 a_j；如果一个都找不到，就输出 -1。

简单来说，就是给数组里的每个小伙伴，找一个能和它“和平共处”（按位与为0）的另一个小伙伴呐！

喵喵的解题思路~ ✨ ​

这道题看起来好像很简单，最直观的想法就是暴力出奇迹嘛！对于数组里的每个 a_i，我们都遍历一遍整个数组，去检查每一个 a_j 是不是和它兼容。

for a_i in a:for a_j in a:if a_i & a_j == 0:// 找到啦！

但是喵~ 看一眼数据范围，n 最大可以到 10^6！O(n^2) 的复杂度肯定会超时到天上去的，这个方法行不通的说！必须想个更聪明的办法才行！

既然题目和位运算（Bitwise Operation）息息相关，那我们的思路也应该往位运算和位掩码（Bitmask）的方向去靠拢，对吧？

我们来分析一下“兼容”的条件：x & y == 0。 这意味着，对于任意一个二进制位，如果 x 在这个位上是 1，那么 y 在这个位上就必须是 0。如果 x 在某个位上是 0，y 在这个位上可以是 0 也可以是 1。

这听起来是不是很耳熟？这不就是说，y 的所有为 1 的位，必须是 x 为 0 的位的子集吗？换句话说，y 必须是 x 的按位取反（~x）的子集掩码（submask）！

举个栗子🌰： 假设 x = 90 (二进制 1011010)。 那么 ~x (假设在 7 位内) 就是 0100101。 我们需要找的 y，它的二进制表示中，所有为 1 的位，都必须在 0100101 的 1 的位置上。 比如 y = 36 (二进制 0100100)，它就是 0100101 的一个子集掩码，所以 90 & 36 == 0。

这样一来，问题就转化成： 对于每一个 a_i，计算出它的补集 complement = ~a_i，然后我们需要快速查询是否存在一个数组中的数 x，使得 x 是 complement 的子集掩码。

现在的问题就是如何快速查询了。这正是子集动态规划（Sum over Subsets DP，简称 SOS DP）大显身手的时候！

我们可以创建一个 dp 数组，dp[mask] 用来存储一个信息：是否存在一个输入数字 x，使得 x 是 mask 的子集掩码？如果存在，dp[mask] 就存这个 x；如果不存在，就存 -1。

我们的目标就是高效地计算出所有 mask 对应的 dp 值。

DP 步骤如下喵：

  1. 初始化：

    • 创建一个 dp 数组，大小为 (1 << 22)，因为 4 * 10^6 小于 2^22。所有元素初始化为 -1。
    • 遍历输入的数组 a。对于每个数字 x，它本身就是 x 的一个子集掩码。所以我们设置 dp[x] = x。

  2. SOS DP 状态转移：

    • 我们的目标是，让 dp[mask] 的信息，从它的所有子集掩码那里“传递”过来。
    • 我们可以通过迭代每一个位 i 来实现。对于每一个 mask，如果它的第 i 位是 1，那么 mask ^ (1 << i) 就是 mask 的一个子集掩码。
    • 如果 dp[mask] 还是 -1（说明 mask 本身不在输入数组里），但 dp[mask ^ (1 << i)] 已经有值了，我们就可以用 dp[mask ^ (1 << i)] 的值来更新 dp[mask]。
    • 这个过程保证了信息从子集掩码流向超集掩码。当整个 DP 过程结束后，dp[mask] 就会存储一个存在于原数组中的 mask 的子集掩码（如果存在的话）。

    伪代码是这样的：

    // i 是二进制位
for i from 0 to MAX_BITS-1:
  // mask 是所有可能的位掩码
  for mask from 0 to MAX_VAL-1:
    // 如果 mask 的第 i 位是 1
    if (mask has i-th bit set):
      // 并且 dp[mask] 还没有被填充
      if dp[mask] == -1:
        // 就从它的子集 mask ^ (1 << i) 继承信息
        dp[mask] = dp[mask ^ (1 << i)]

  3. 查询答案：

    • 当 dp 数组构建完毕后，我们就可以轻松地找到答案啦！
    • 遍历原始数组 a 中的每一个元素 a_i。
    • 计算它的补集 complement = a_i ^ ALL_BITS（ALL_BITS 是一个所有位都为1的掩码，比如 (1 << 22) - 1）。
    • 我们需要的答案就是 dp[complement]！它要么是 -1，要么就是一个满足条件的兼容数字。

这个思路是不是非常巧妙呢？通过一次预处理，我们把每次查询的复杂度降到了 O(1)，总的复杂度就变得可以接受啦！

代码魔法详解喵 ✨ ​

cpp
#include <iostream>
#include <vector>
#include <numeric>

// 设置表示输入值所需的最大位数，喵~
// a_i 的最大值是 4 * 10^6
// 2^21 = 2,097,152
// 2^22 = 4,194,304
// 所以 22 位就足够啦！
const int MAX_BITS = 22;
// DP 数组的大小，覆盖所有可能的 22 位掩码
const int MAX_VAL = 1 << MAX_BITS;

int main() {
    // 使用快速 I/O，让程序跑得飞快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 存储原始数组，方便最后按顺序输出结果
    std::vector<int> a(n);

    // dp[mask] 将存储一个来自输入数组 `a` 的数字 `x`，
    // 满足 `x` 是 `mask` 的一个子集掩码 (submask)。
    // 如果不存在这样的 `x`，dp[mask] 就保持为 -1。
    std::vector<int> dp(MAX_VAL, -1);

    // 初始化 DP 数组。对于输入数组中的每个数 `x`，
    // 它本身就是 `x` 的子集掩码，所以我们设置 dp[x] = x。
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        dp[a[i]] = a[i];
    }

    // Sum over Subsets DP 的计算过程，喵~
    // 对于每个 mask，我们要找到它是否存在一个出现在输入数组中的子集掩码。
    // 这是通过将值从子集掩码传播到超集掩码来完成的。

    // 遍历每一个二进制位 `i`
    for (int i = 0; i < MAX_BITS; ++i) {
        // 遍历每一种可能的掩码
        for (int mask = 0; mask < MAX_VAL; ++mask) {
            // 如果 mask 的第 i 位是 1，那么 `mask` 就是 `mask ^ (1 << i)` 的超集掩码，
            // 我们可以从子集那里传播值过来。
            if ((mask >> i) & 1) {
                // 如果 dp[mask] 还没有被填充过，
                // 就用它的子集 `mask ^ (1 << i)` 的值来填充。
                // 这样做可以保证，如果 `mask` 本身就在输入数组里，它的值会被保留下来。
                if (dp[mask] == -1) {
                    dp[mask] = dp[mask ^ (1 << i)];
                }
            }
        }
    }

    // 一个所有位都是 1 的掩码，用于计算按位补集
    const int ALL_BITS = MAX_VAL - 1;

    // 对原始数组中的每个元素，找到它的兼容伙伴
    for (int i = 0; i < n; ++i) {
        // `x` 和 `y` 兼容，当且仅当 (x & y) == 0
        // 这等价于 `y` 是 `~x` 的子集掩码
        int current_num = a[i];
        // 计算当前数字的补集掩码
        int complement_mask = current_num ^ ALL_BITS;
        
        // dp[complement_mask] 存储的就是一个来自输入数组的数，
        // 并且这个数是 `complement_mask` 的子集掩码，
        // 也就是我们想找的那个与 `current_num` 兼容的数！
        int result = dp[complement_mask];

        if (i > 0) {
            std::cout << " ";
        }
        std::cout << result;
    }
    std::cout << std::endl;

    return 0;
}

时空魔法消耗分析喵 ⏳ ​

  • 时间复杂度: O(N + K * 2^K) 的说。 其中 N 是输入数组的大小，K 是我们处理的位数（这里是22）。 O(N) 用于读取输入并初始化 dp 数组。 核心的 SOS DP 部分有两个嵌套循环，外层循环 K 次，内层循环 2^K 次，所以是 O(K * 2^K)。 最后输出答案是 O(N)。 总的来说，复杂度由 DP 部分主导，是 O(N + K * 2^K)。

  • 空间复杂度: O(N + 2^K) 的说。 我们需要一个大小为 N 的数组 a 来存储输入，还需要一个大小为 2^K 的 dp 数组。所以空间开销是 O(N + 2^K)。

喵喵的小课堂 📚 ​

这道题真是一道非常经典的 SOS DP 入门题呢！通过它我们可以学到很多东西哦！

  1. 问题转化能力: 解题的关键在于将 a & b == 0 这个条件，巧妙地转化为 b 是 ~a 的子集掩码。这种思维转换在处理位运算问题时非常重要！

  2. Sum over Subsets (SOS) DP: 这是解决与子集相关问题的强大武器！它的核心思想是通过迭代位，将信息从子集传递到超集（或者反过来）。当你遇到需要对一个掩码的所有子集/超集进行计算或查询时，都可以考虑使用 SOS DP。它的 O(K * 2^K) 复杂度远比朴素的 O(3^K) 枚举子集要高效！

  3. 位运算基础: 熟练掌握 & (与), | (或), ^ (异或), ~ (取反), << (左移), >> (右移) 这些操作是解决此类问题的基本功。比如本题中用 ^ 来计算补集，用 >> 和 & 来检查某一位是否为1。

希望这篇题解能帮助你理解这道题目背后的思想！继续加油，在算法的世界里不断探索吧，喵~！💖

Released under the MIT License.

Copyright © 2024-present Moe