题目描述

小红需要根据每位病人的症状开药。

每位病人的症状由一个长度为的 01 串表示：第位为 1，说明第个身体部位有症状；为 0，说明该部位健康。

每种药同样由一个长度为的 01 串表示：第位为 1，说明这种药可以治疗第个部位。

对于每位病人，需要从种药中选择若干种，使这些药能够覆盖该病人的所有症状，并求出所需药物的最少数量。如果无论怎样选择药物都无法治愈该病人，则输出 -1。

数据范围：

，表示病人的数量；
，表示身体部位（症状种类）的数量；
，表示药物的数量。

思路：状态压缩 + 枚举子集

这道题中、，范围都比较小，因此可以使用二进制状态压缩。

1. 将 01 串转换为二进制掩码

病人的症状和药物能够治疗的部位都可以用一个整数表示。

例如，字符串 1011 中第、、位为 1，可以转换为对应的二进制掩码。这样，多个药物治疗范围的并集就可以通过按位或运算 | 得到。

需要注意的是，代码直接令字符串下标对应二进制的第位。位的高低顺序并不影响结果，只要病人和药物采用同一种转换方式即可。

2. 预处理每个药物子集

种药一共有个子集。对于每个子集 subset，预处理两个信息：

cover[subset]：该子集中的全部药物可以治疗哪些部位；
medicineCnt[subset]：该子集包含多少种药。

为了避免每次都重新遍历子集中的所有药物，可以取出 subset 的最低位 1：

int lowbit = subset & -subset;

删掉最低位 1 后得到 previous。于是当前子集可以由 previous 加上一种药转移得到：

cover[subset] = cover[previous] | medicines[medicineIndex];
medicineCnt[subset] = medicineCnt[previous] + 1;

3. 为每位病人寻找最少用药数

枚举所有药物子集。如果一个子集能够覆盖病人的全部症状，就用它包含的药物数量更新答案。

设病人的症状掩码为 patientMask，药物子集的治疗范围为 cover[subset]，那么覆盖全部症状的判断条件为：

(cover[subset] & patientMask) == patientMask

按位与之后仍然等于 patientMask，说明病人的每一个症状位都包含在该药物子集的治疗范围中。

如果遍历完所有子集仍然没有找到可行方案，就输出 -1。

正确性说明

程序枚举了种药构成的全部个子集，因此任意一种可能的开药方案都不会遗漏。对于每个子集，cover 准确记录其中所有药物治疗范围的并集；覆盖判断成立时，该方案一定能治愈当前病人。程序在所有可行方案中取药物数量的最小值，所以得到的就是最少用药数；如果没有任何子集满足条件，则该病人确实无法被治愈。

复杂度分析

将所有病人和药物的 01 串转换为掩码需要的时间；
预处理全部药物子集需要的时间；
每位病人枚举全部药物子集需要的时间，共需要。

因此：

时间复杂度：，主要部分为；
空间复杂度：。

代码

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 将长度为 m 的 01 串转换为二进制掩码。
// 字符串的第 i 位对应整数的第 i 个二进制位。
int string2mask(const string &s) {
    int mask = 0;

    for (int i = 0; i < static_cast<int>(s.size()); ++i) {
        if (s[i] == '1') {
            mask |= (1 << i);  // 将第 i 个身体部位标记为 1
        }
    }

    return mask;
}

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

    int n, m;
    cin >> n >> m;

    // patients[i] 表示第 i 位病人的症状集合。
    vector<int> patients(n);

    for (int i = 0; i < n; ++i) {
        string symptoms;
        cin >> symptoms;
        patients[i] = string2mask(symptoms);
    }

    int k;
    cin >> k;

    // medicines[i] 表示第 i 种药可以治疗的部位集合。
    vector<int> medicines(k);

    for (int i = 0; i < k; ++i) {
        string symptoms;
        cin >> symptoms;
        medicines[i] = string2mask(symptoms);
    }

    // k 种药共有 2^k 个子集，subset 的第 i 位表示是否选择第 i 种药。
    int total = 1 << k;

    // cover[subset]：subset 中所有药物能够治疗的部位并集。
    // medicineCnt[subset]：subset 中包含的药物数量。
    vector<int> cover(total, 0);
    vector<int> medicineCnt(total, 0);

    // 通过删除最低位的 1，从较小子集递推得到当前子集的信息。
    for (int subset = 1; subset < total; ++subset) {
        int lowbit = subset & -subset;          // 取出最低位的 1
        int previous = subset ^ lowbit;         // 删除最低位的 1
        int medicineIndex = __builtin_ctz(lowbit);  // 该位对应的药物下标

        cover[subset] = cover[previous] | medicines[medicineIndex];
        medicineCnt[subset] = medicineCnt[previous] + 1;
    }

    // 对每位病人枚举所有开药方案，寻找药物数量最少的可行方案。
    for (int patientMask : patients) {
        int ans = k + 1;  // k + 1 表示当前还没有找到可行方案

        for (int subset = 0; subset < total; ++subset) {
            // 当前方案的药物数不可能优于已有答案，直接跳过。
            if (medicineCnt[subset] >= ans) continue;

            // 病人的每个症状都在当前药物子集的治疗范围中。
            if ((cover[subset] & patientMask) == patientMask) {
                ans = medicineCnt[subset];
            }
        }

        if (ans == k + 1)
            cout << -1 << '\n';
        else
            cout << ans << '\n';
    }

    return 0;
}

示例分析

输入：

输出：

1
-1
2

第一位病人的症状可以由第一种药单独覆盖，因此答案为 1；
第二位病人的症状无法被任何药物组合完全覆盖，因此答案为 -1；
第三位病人需要同时使用两种药，因此答案为 2。

总结

本题的关键是注意到药物数量，可以枚举全部个药物子集。先用状态压缩表示症状和治疗范围，再预处理每个药物子集的覆盖范围与药物数量，就能让所有病人复用同一份子集信息。

需要掌握的三个核心操作是：

使用按位或 | 合并多种药的治疗范围；
使用 subset & -subset 取出最低位的 1，快速递推子集信息；
使用 (cover & patientMask) == patientMask 判断是否完全覆盖病人的症状。

这类“元素数量较少、需要枚举所有选择方案”的问题，通常都可以考虑状态压缩与子集枚举。

TK的小站

牛客每日一题-医生