题解 | #整数覆盖#

题目链接

题目描述

给定 $n$ 个正整数。我们定义一个正整数 $A$ “包含” 另一个正整数 $B$ ，当且仅当 (A | B) == A，其中 | 是按位或运算。这个条件的含义是，在二进制表示下，所有 $B$ 中为 $1$ 的位，在 $A$ 中也必须为 $1$ 。

任务是从这 $n$ 个数中选出尽可能少的数，组成一个集合，使得原来 $n$ 个数中的每一个数，都至少被这个新集合中的某一个数所“包含”。

输入:

第一行一个正整数 $n$ 。
第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$ 。

输出:

一个整数，表示最少需要选出的数字个数。

解题思路

这是一个利用位运算和动态规划解决的集合覆盖问题。一个朴素的 $O(n^2)$ 做法是检查每对数，但这在 $n$ 较大时会超时。考虑到数值范围 $A_i < 2^{18}$ ，我们可以使用 Sum over Subsets (SOS) DP（或称为位运算DP）来优化。

核心思想是：一个数 $a_i$ 如果能被集合中另一个不等于它的数 $a_j$ 包含，那么我们就不需要选择 $a_i$ 。我们只需要统计有多少个数是无法被其他任何数包含的。

高效的算法步骤如下：

预处理：
- 首先对输入的数进行去重，因为重复的数不影响覆盖关系。
- 创建一个大小为 $2^{18}$ 的布尔数组 present，present[i] = true 表示数字 i 存在于输入中。
动态规划 (SOS DP)：
- 创建一个大小为 $2^{18}$ 的布尔数组 sos，sos[mask] 的含义是：数字 mask 或 mask 的某个超集是否存在于输入中。
- 初始化 sos 数组，令 sos[i] = present[i]。
- 通过动态规划填充 sos 数组。我们从高位到低位遍历所有二进制位 i，再从大到小遍历所有 mask。状态转移方程可以理解为：如果 mask 的第 i 位为 0，那么它的超集 mask | (1 << i) 的信息可以传递给它。
- if (!(mask & (1 << i))) sos[mask] |= sos[mask | (1 << i)];
- 经过这个过程，sos[mask] 就正确地存储了所需信息。
计数：
- 遍历所有去重后的输入数 x。
- 对于每个 x，我们需要判断是否存在一个严格超集 y ( $y \neq x$ 且 $(y|x) == y$ ) 在输入中。
- 一个 $x$ 的严格超集，必然是在 $x$ 的某个为 0 的位上为 1。
- 所以，我们遍历 x 的所有为 0 的二进制位 i，构造一个 mask = x | (1 << i)。
- 我们查询 sos[mask]。如果 sos[mask] 为 true，说明存在一个输入中的数 y 是 mask 或 mask 的超集，这个 y 必然是 x 的严格超集。因此 x 可以被覆盖。
- 如果在检查完 x 所有为 0 的位后，都没有找到能覆盖它的数，那么 x 就是必须选择的。
- 统计所有必须选择的数的个数即为答案。

代码

c++
java
python

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

using namespace std;

const int MAX_VAL = 262144; // 2^18
bool present[MAX_VAL];
bool sos[MAX_VAL];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    set<int> unique_nums_set;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        unique_nums_set.insert(a);
    }
    
    vector<int> a(unique_nums_set.begin(), unique_nums_set.end());

    for (int x : a) {
        present[x] = true;
    }

    for (int i = 0; i < MAX_VAL; ++i) {
        sos[i] = present[i];
    }

    for (int i = 0; i < 18; ++i) {
        for (int mask = MAX_VAL - 1; mask >= 0; --mask) {
            if (!(mask & (1 << i))) {
                sos[mask] |= sos[mask | (1 << i)];
            }
        }
    }

    int ans = 0;
    for (int x : a) {
        bool is_covered_by_proper_superset = false;
        for (int i = 0; i < 18; ++i) {
            if (!(x & (1 << i))) {
                if (sos[x | (1 << i)]) {
                    is_covered_by_proper_superset = true;
                    break;
                }
            }
        }
        if (!is_covered_by_proper_superset) {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Integer> uniqueNums = new HashSet<>();
        for (int i = 0; i < n; i++) {
            uniqueNums.add(sc.nextInt());
        }

        int maxVal = 262144; // 2^18
        boolean[] sos = new boolean[maxVal];

        for (int x : uniqueNums) {
            sos[x] = true;
        }

        for (int i = 0; i < 18; i++) {
            for (int mask = maxVal - 1; mask >= 0; mask--) {
                if ((mask & (1 << i)) == 0) {
                    sos[mask] |= sos[mask | (1 << i)];
                }
            }
        }

        int ans = 0;
        for (int x : uniqueNums) {
            boolean isCovered = false;
            for (int i = 0; i < 18; i++) {
                if ((x & (1 << i)) == 0) {
                    if (sos[x | (1 << i)]) {
                        isCovered = true;
                        break;
                    }
                }
            }
            if (!isCovered) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

n = int(input())
a = list(map(int, input().split()))

unique_a = sorted(list(set(a)))

MAX_VAL = 262144 # 2^18
sos = [False] * MAX_VAL

for x in unique_a:
    sos[x] = True
    
for i in range(18):
    for mask in range(MAX_VAL - 1, -1, -1):
        if not (mask & (1 << i)):
            sos[mask] |= sos[mask | (1 << i)]

ans = 0
for x in unique_a:
    is_covered = False
    for i in range(18):
        if not (x & (1 << i)):
            if sos[x | (1 << i)]:
                is_covered = True
                break
    if not is_covered:
        ans += 1
        
print(ans)

算法及复杂度

算法：位运算动态规划 (Sum over Subsets DP)
时间复杂度： $O(N + W \cdot \log W)$ ，其中 $N$ 是输入数字个数， $W$ 是数值上限 ( $2^{18}$ )。 $O(N)$ 用于读取和去重， $O(W \log W)$ 用于DP计算和最终检查。
空间复杂度： $\mathcal{O}(W)$ ，需要数组来存储DP状态。