京东 · 模拟 · 算法编程题
京东 模拟 n ≤ 20 时限 1 秒 / 256 MB

题目描述

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

输入输出

输入描述
第一行输入一个正整数 n ，代表症状的数量。
第二行输入一个长度为 n 的01串，第 i 位是'1'代表小红目前有第 i 个症状，第 i 位是'0'代表没有该症状。
第三行输入一个正整数 m ，代表药的数量。
接下来的 2*m 行，每2行描述一副药：
第一行输入一个长度为 n 的01串，代表该药能治疗的症状。'1'代表可以治疗，'0'代表不能治疗。
第二行输入一个长度为 n 的01串，代表该药会产生的副作用。'1'代表会产生该症状，'0'代表不会产生。
接下来的一行，输入一个正整数 q ，代表小红服用的药数量。
接下来的 q 行，每行输入一个正整数 u ，代表小红服用了第 u 副药。
1≤ n ≤ 20
1≤ m,q ≤ 10^4
1≤ a_i ,u≤ m
保证每副药副作用产生的症状和该药治疗的症状是不会重复的，即不会存在同一个位置的两个01串都是'1'。
输出描述
输出 q 行，每行输入一个正整数，代表当前小红服用药后，身体有多少症状。

样例共 1 组

样例 1 · 最开始小红有第二个、第四个症状。 开始小红服用了第二副药，治好了这两个症状，但新增了第一个症状。目前症状数量为1。 然后小红服用了第三副药，治好了第一个症状，并没有新增症状。目前症状数量为0。 最后小红服用了第一副药。由于小红没有症状，所以没有治疗，但又新增了第三个症状，目前症状数量为1。
输入
4
0101
3
1100
0010
0101
1000
1001
0000
3
2
3
1
输出
1
0
1

算法解析依据充分

考点：模拟

数据规模 n ≤ 20 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：m ≤ 1e4，q ≤ 1e4，n ≤ 20
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：模拟

不涉及复杂算法，把题目描述的流程原样翻译成代码逐步执行即可。

思路框架（模拟 通法 · 非本题专属）

  1. 用变量记录题目要求的「状态」（当前值、剩余数量、当前位置等）。
  2. 按题面给出的顺序，把每一步操作写成一段代码，逐条执行。
  3. 每一步执行后更新状态，并在题目要求的位置输出或累计答案。
  4. 注意循环的边界：执行多少次、何时终止、是否能终止。

实现要点：结构上通常是一个外层循环包住若干 if/else 分支；只要状态定义清楚，正确率很高。

复杂度：时间 O(操作次数) ｜ 空间 O(状态数)

该范式的通法易错点

  • 终止条件写错导致死循环或漏做最后一次操作。
  • 状态更新顺序颠倒（先改了下标又用旧下标）。
  • 题目里「最多 / 恰好 / 至少」的语义差别没区分。

对照本题

  • 数据规模 n ≤ 20，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。

样例解读

样例 1：输入 4 / 0101 / 3 / 1100 / 0010 / 0101 / 1000 / 1001 / 0000 / 3 / 2 / 3 / 1 → 输出 1 / 0 / 1

最开始小红有第二个、第四个症状。

开始小红服用了第二副药，治好了这两个症状，但新增了第一个症状。目前症状数量为1。

然后小红服用了第三副药，治好了第一个症状，并没有新增症状。目前症状数量为0。

最后小红服用了第一副药。由于小红没有症状，所以没有治疗，但又新增了第三个症状，目前症状数量为1。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年秋招-京东-技术通用岗位-第二批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解