题目链接

小红吃药

题目描述

小红有 种可能的症状。她的初始症状由一个长度为 的 01 串表示。现有 种药，每种药有两个属性：

  1. 治疗范围：一个长度为 的 01 串，'1' 表示该药可以治疗对应症状。
  2. 副作用：一个长度为 的 01 串，'1' 表示服用该药会产生对应症状。

题目保证一种药的治疗症状和副作用症状不会重叠。

小红会按顺序服用 副药。你需要计算并输出她在每次服药后，还剩下多少种症状。

解题思路

这是一个状态更新的模拟问题。由于症状的状态只有“有”和“没有”两种，非常适合使用位掩码 (Bitmask) 来表示和处理。

1. 使用位掩码表示状态

  • 症状状态：我们可以用一个整数来表示小红的所有症状。这个整数的二进制表示中，从右到左的第 i-th 位（0-indexed）为 1，代表小红有第 i+1 种症状；为 0 则代表没有。
  • 药品属性：同样，每种药的治疗范围和副作用也可以分别用一个位掩码来表示。

例如，如果 n=4，初始症状是 "0101"，那么对应的症状位掩码就是二进制的 0101，即十进制的 5。

2. 使用位运算进行状态转移

当小红服用一种药时，她的症状状态会发生变化。这种变化可以通过位运算高效地完成。

  • 治疗过程： 假设小红当前的症状掩码是 current_symptoms，所服用药物的治疗掩码是 cure_mask。 治疗的效果是：如果某个症状小红有，并且药物能治，那么这个症状就消失了。这等价于将 current_symptoms 中，那些在 cure_mask 中也为 1 的位，全部清零。 这个操作可以通过按位与（AND）和按位非（NOT）实现： current_symptoms = current_symptoms & (~cure_mask); ~cure_mask 会得到一个掩码，其中原 cure_mask 中为 1 的位都变为 0，其余为 1。再与 current_symptoms 相与，就能精确地“关闭”需要治疗的症状位，而不影响其他位。

  • 副作用过程： 假设药物的副作用掩码是 side_effect_mask。 副作用的效果是：无论小红之前是否有这些症状，现在都会拥有由副作用引起的所有症状。这等价于将 current_symptoms 中，那些在 side_effect_mask 中为 1 的位，全部置为 1。 这个操作可以通过按位或（OR）实现： current_symptoms = current_symptoms | side_effect_mask;

3. 统计症状数量

在每次更新完 current_symptoms 后，我们需要计算当前还剩多少症状。这等价于计算 current_symptoms 的二进制表示中有多少个 '1'。这个操作被称为 "population count" 或 "popcount"。大多数语言都提供了高效的内建函数来完成这个任务。

4. 整体流程

  1. 将输入的初始症状 01 串、每种药的治疗范围和副作用 01 串，全部转换为整数位掩码。
  2. 循环 次，模拟每次服药的过程。
  3. 在每次循环中，根据服用的药，使用上述的位运算更新 current_symptoms。
  4. 计算并输出更新后 current_symptoms 的 popcount。

代码

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#if defined(__GNUC__) || defined(__clang__)
#include <strings.h>
#define popcount __builtin_popcount
#else
// Fallback for other compilers like MSVC
int popcount(int n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}
#endif

using namespace std;

int string_to_mask(const string& s) {
    int mask = 0;
    for (char c : s) {
        mask = (mask << 1) | (c - '0');
    }
    return mask;
}

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

    int n;
    cin >> n;
    string initial_symptoms_str;
    cin >> initial_symptoms_str;
    int current_symptoms = string_to_mask(initial_symptoms_str);

    int m;
    cin >> m;
    vector<pair<int, int>> drugs(m);
    for (int i = 0; i < m; ++i) {
        string cure_str, side_effect_str;
        cin >> cure_str >> side_effect_str;
        drugs[i] = {string_to_mask(cure_str), string_to_mask(side_effect_str)};
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int drug_idx;
        cin >> drug_idx;
        drug_idx--; // 0-indexed

        int cure_mask = drugs[drug_idx].first;
        int side_effect_mask = drugs[drug_idx].second;

        // Apply cure
        current_symptoms &= ~cure_mask;
        // Apply side effect
        current_symptoms |= side_effect_mask;

        cout << popcount(current_symptoms) << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        String initialSymptomsStr = sc.next();
        int currentSymptoms = Integer.parseInt(initialSymptomsStr, 2);

        int m = sc.nextInt();
        int[][] drugs = new int[m][2]; // 0: cure, 1: side effect
        for (int i = 0; i < m; i++) {
            String cureStr = sc.next();
            String sideEffectStr = sc.next();
            drugs[i][0] = Integer.parseInt(cureStr, 2);
            drugs[i][1] = Integer.parseInt(sideEffectStr, 2);
        }

        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int drugIdx = sc.nextInt() - 1; // 0-indexed

            int cureMask = drugs[drugIdx][0];
            int sideEffectMask = drugs[drugIdx][1];

            // Apply cure
            currentSymptoms &= ~cureMask;
            // Apply side effect
            currentSymptoms |= sideEffectMask;

            System.out.println(Integer.bitCount(currentSymptoms));
        }
    }
}

import sys

def solve():
    try:
        n = int(sys.stdin.readline())
        initial_symptoms_str = sys.stdin.readline().strip()
        current_symptoms = int(initial_symptoms_str, 2)

        m = int(sys.stdin.readline())
        drugs = []
        for _ in range(m):
            cure_str = sys.stdin.readline().strip()
            side_effect_str = sys.stdin.readline().strip()
            drugs.append((int(cure_str, 2), int(side_effect_str, 2)))

        q = int(sys.stdin.readline())
        queries = [int(sys.stdin.readline()) for _ in range(q)]

    except (IOError, ValueError):
        return
        
    for drug_idx in queries:
        drug_idx -= 1 # 0-indexed
        
        cure_mask, side_effect_mask = drugs[drug_idx]
        
        # Apply cure
        current_symptoms &= ~cure_mask
        # Apply side effect
        current_symptoms |= side_effect_mask
        
        print(bin(current_symptoms).count('1'))

solve()

算法及复杂度

  • 算法：模拟、位运算

  • 时间复杂度：。

    • 和 用于读取输入并将其转换为位掩码。
    • 用于处理 次服药查询，每次查询的位运算和 popcount 都是常数时间操作（对于固定大小的整数）。

  • 空间复杂度：。

    • 需要 的空间来存储 种药的治疗和副作用掩码。