小红吃药

[题目链接](https://www.nowcoder.com/practice/ea822e4a974e4ab0bc72c203adce7d44)

思路

本题是一道位运算模拟题。

问题分析

小红有 种症状，用一个 01 串表示当前的症状状态。每副药有两个属性：

• 治疗掩码：能治好哪些症状（对应位清零）
• 副作用掩码：会新增哪些症状（对应位置一）

题目保证同一副药的治疗掩码和副作用掩码不会在同一位上都为 1。

位运算建模

将症状状态和每副药的治疗/副作用都用二进制整数表示。设当前症状状态为 ，服用第 副药时：

$$

• ：把能治好的症状位清零
• ：把副作用对应的症状位置一

每次操作后，统计 中 1 的个数即为当前症状数量。

注意事项

最大可能超过 64 位整数的范围（题目未明确说明上限，但 01 串长度可达 1000），因此：

• C++ 中使用 bitset<1000>
• Java 中使用 BigInteger
• Python 原生支持任意长度整数
• JavaScript 使用 BigInt

代码

[sol-C++]

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    char s[1001];
    scanf("%s", s);
    bitset<1000> state;
    for(int i = 0; i < n; i++){
        if(s[i] == '1') state.set(i);
    }
    int m;
    scanf("%d", &m);
    vector<bitset<1000>> cure(m), side(m);
    for(int i = 0; i < m; i++){
        scanf("%s", s);
        for(int j = 0; j < n; j++){
            if(s[j] == '1') cure[i].set(j);
        }
        scanf("%s", s);
        for(int j = 0; j < n; j++){
            if(s[j] == '1') side[i].set(j);
        }
    }
    int q;
    scanf("%d", &q);
    while(q--){
        int x;
        scanf("%d", &x);
        x--;
        state = (state & ~cure[x]) | side[x];
        int cnt = 0;
        for(int i = 0; i < n; i++){
            if(state[i]) cnt++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

[sol-Java]

import java.util.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        BigInteger state = BigInteger.ZERO;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') state = state.setBit(i);
        }
        int m = sc.nextInt();
        BigInteger[] cure = new BigInteger[m];
        BigInteger[] side = new BigInteger[m];
        for (int i = 0; i < m; i++) {
            String cs = sc.next();
            cure[i] = BigInteger.ZERO;
            for (int j = 0; j < n; j++) {
                if (cs.charAt(j) == '1') cure[i] = cure[i].setBit(j);
            }
            String ss = sc.next();
            side[i] = BigInteger.ZERO;
            for (int j = 0; j < n; j++) {
                if (ss.charAt(j) == '1') side[i] = side[i].setBit(j);
            }
        }
        int q = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int x = sc.nextInt() - 1;
            state = state.andNot(cure[x]).or(side[x]);
            sb.append(state.bitCount()).append('\n');
        }
        System.out.print(sb);
    }
}

[sol-Python3]

import sys
input = sys.stdin.readline

n = int(input())
s = input().strip()
state = int(s, 2)

m = int(input())
cure = [0] * m
side = [0] * m
for i in range(m):
    cs = input().strip()
    cure[i] = int(cs, 2)
    ss = input().strip()
    side[i] = int(ss, 2)

q = int(input())
out = []
for _ in range(q):
    x = int(input()) - 1
    state = (state & ~cure[x]) | side[x]
    out.append(str(bin(state).count('1')))
print('\n'.join(out))

[sol-JavaScript]

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const n = parseInt(lines[idx++]);
    const s = lines[idx++];
    let state = BigInt('0b' + s);
    const m = parseInt(lines[idx++]);
    const cure = new Array(m);
    const side = new Array(m);
    for (let i = 0; i < m; i++) {
        cure[i] = BigInt('0b' + lines[idx++]);
        side[i] = BigInt('0b' + lines[idx++]);
    }
    const q = parseInt(lines[idx++]);
    const out = [];
    for (let i = 0; i < q; i++) {
        const x = parseInt(lines[idx++]) - 1;
        state = (state & ~cure[x]) | side[x];
        let cnt = 0;
        let tmp = state;
        while (tmp > 0n) {
            tmp &= (tmp - 1n);
            cnt++;
        }
        out.push(cnt);
    }
    console.log(out.join('\n'));
});

复杂度分析

• 时间复杂度：，其中 是机器字长（通常为 64）。每次服药的位运算和 popcount 操作耗时 。
• 空间复杂度：，存储 副药的治疗和副作用掩码。