题解 | #小红吃药#

题目链接

小红吃药

题目描述

小红准备买药治病。已知共有 $n$ 种症状和 $m$ 种药，第 $i$ 种药可以治疗一些症状，但可能会导致一些副作用，添加一些新的症状。小红依次服用了一些药，请你告诉小红，当她每次服用一副药时，当前还有多少症状？

输入:

第一行输入一个正整数 $n$ ，代表症状的数量
第二行输入一个长度为 $n$ 的01串，第 $i$ 位是'1'代表小红目前有第 $i$ 个症状，'0'代表没有该症状
第三行输入一个正整数 $m$ ，代表药的数量
接下来的 $2m$ 行，每2行描述一副药：
- 第一行输入一个长度为 $n$ 的01串，代表该药能治疗的症状。'1'代表可以治疗，'0'代表不能治疗
- 第二行输入一个长度为 $n$ 的01串，代表该药会产生的副作用。'1'代表会产生该症状，'0'代表不会产生
接下来的一行，输入一个正整数 $k$ ，代表小红服用的药数量
接下来的 $k$ 行，每行输入一个正整数，代表小红服用了第几副药

输出:

输出 $k$ 行，每行输出一个正整数，代表当前小红服用药后，身体有多少症状

解题思路

这是一个模拟问题，可以通过以下步骤解决：

关键发现：
- 需要用位运算处理症状的变化
- 每种药有治疗效果和副作用两个方面
- 药物的作用顺序会影响最终结果
解题策略：
- 使用二进制表示症状状态
- 按顺序模拟每次服药过程
- 计算每次服药后的症状数量
具体步骤：
- 读入初始症状状态
- 读入每种药的治疗效果和副作用
- 模拟每次服药，更新症状状态
- 统计当前症状数量

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    string initial;
    cin >> initial;
    
    // 将初始症状转换为整数
    int state = 0;
    for(int i = 0; i < n; i++) {
        if(initial[i] == '1') {
            state |= (1 << i);
        }
    }
    
    int m;
    cin >> m;
    vector<pair<int, int>> medicines(m);  // 每副药的治疗效果和副作用
    
    // 读入每副药的信息
    for(int i = 0; i < m; i++) {
        string treat, side;
        cin >> treat >> side;
        
        int treat_mask = 0, side_mask = 0;
        for(int j = 0; j < n; j++) {
            if(treat[j] == '1') treat_mask |= (1 << j);
            if(side[j] == '1') side_mask |= (1 << j);
        }
        medicines[i] = {treat_mask, side_mask};
    }
    
    int k;
    cin >> k;
    // 模拟服药过程
    while(k--) {
        int med;
        cin >> med;
        med--;  // 转换为0-based索引
        
        // 更新症状状态
        state &= ~(state & medicines[med].first);  // 去除被治愈的症状
        state |= medicines[med].second;  // 添加副作用症状
        
        // 统计当前症状数量
        cout << __builtin_popcount(state) << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String initial = sc.next();
        
        // 将初始症状转换为整数
        int state = 0;
        for(int i = 0; i < n; i++) {
            if(initial.charAt(i) == '1') {
                state |= (1 << i);
            }
        }
        
        int m = sc.nextInt();
        int[][] medicines = new int[m][2];  // 每副药的治疗效果和副作用
        
        // 读入每副药的信息
        for(int i = 0; i < m; i++) {
            String treat = sc.next();
            String side = sc.next();
            
            int treat_mask = 0, side_mask = 0;
            for(int j = 0; j < n; j++) {
                if(treat.charAt(j) == '1') treat_mask |= (1 << j);
                if(side.charAt(j) == '1') side_mask |= (1 << j);
            }
            medicines[i][0] = treat_mask;
            medicines[i][1] = side_mask;
        }
        
        int k = sc.nextInt();
        // 模拟服药过程
        while(k-- > 0) {
            int med = sc.nextInt() - 1;  // 转换为0-based索引
            
            // 更新症状状态
            state &= ~(state & medicines[med][0]);  // 去除被治愈的症状
            state |= medicines[med][1];  // 添加副作用症状
            
            // 统计当前症状数量
            System.out.println(Integer.bitCount(state));
        }
    }
}

def count_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

n = int(input())
initial = input()

# 将初始症状转换为整数
state = 0
for i in range(n):
    if initial[i] == '1':
        state |= (1 << i)

m = int(input())
medicines = []  # 每副药的治疗效果和副作用

# 读入每副药的信息
for _ in range(m):
    treat = input()
    side = input()
    
    treat_mask = 0
    side_mask = 0
    for i in range(n):
        if treat[i] == '1':
            treat_mask |= (1 << i)
        if side[i] == '1':
            side_mask |= (1 << i)
    medicines.append((treat_mask, side_mask))

k = int(input())
# 模拟服药过程
for _ in range(k):
    med = int(input()) - 1  # 转换为0-based索引
    
    # 更新症状状态
    state &= ~(state & medicines[med][0])  # 去除被治愈的症状
    state |= medicines[med][1]  # 添加副作用症状
    
    # 统计当前症状数量
    print(count_bits(state))

算法及复杂度

算法：位运算 + 模拟
时间复杂度： $\mathcal{O}(k)$ - k 是服药次数，每次服药需要常数时间更新状态
空间复杂度： $\mathcal{O}(m)$ - m 是药品数量，需要存储每种药的信息

注意：

使用位运算可以高效处理症状的添加和删除
注意药品编号需要转换为0-based索引
每次服药后需要先去除治愈的症状，再添加副作用症状