京东笔试-买药

mengzhuo / 2023-08-20 / 原文

京东笔试-买药

题目

题目的大概意思是，小红有一些症状，他要吃一些药来治病，吃药会治好一些症状，但是也吃药的副作用会带来别的症状

第一行输入n，代表症状的数量
第二行输入长度为n的01串，代表小红的症状（1 有症状；0 无症状）
第三行输入m，代表药的数量
接下来的2*m行，每2行描述一副药:
第一行输入一个长度为n的01串，代表该药能治疗的症状。1代表可以治疗，0代表不能治疗
第二行输入一个长度为n的01串，代表该药会产生的副作用。1代表会产生该症状，0代表不会产生。
接下来的一行，输入一个正整数q，代表小红服用的药数量
接下来的q行，每行输入一个正整数u，代表小红服用了第u副药

输入

输出

1
0
1

思路

看到题目用01串来表示症状，并且药可以治疗和会引起的症状也用01串来表示，我的第一反应是：可不可以用位运算来表示这个过程。后来仔细想了一下，还真可以。

首先能想到的是药物带来的副作用可以用与运算表示，比如：现在症状是0101，药物的副作用是0010，那最终的症状就是0101 | 0010 = 0111。

治疗症状怎么表示呢？如果症状是1010，能治疗的症状表示为1100，那么第一个位置的症状应该被治疗，在位运算中，亦或运算会将相同的位变为0，1010 ^ 1100 = 1001但是亦或运算带来一个副作用：为0的症状且能被治疗的，会变成1，所以我们把结果在和原来的症状进行或运算，就能得到正确的结果了也就是1010 ^ 1100 & 1010 = 0001。

如果我们用m表示状态，用a表示能治疗的症状，用b表示副作用，那么每次吃药后新的症状就是m = m ^ a & m | b

代码

n = int(input())
status = int('0b' + input(), 2)

p = int(input())
medicinal = [(int('0b' + input(), 2), int('0b' + input(), 2)) for i in range(p)]

q = int(input())
for i in range(q):
    u = int(input()) - 1

    status = status ^ medicinal[u][0] & status | medicinal[u][1]
    print(bin(status).count('1'))