医生时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红是一名医生。现在小红对于每个病人的症状用一个长度为m mm的01 0101串表示第i ii个字符代表第i ii个身体部位的症状0 00代表健康1 11代表不健康。一共有k kk种药每种药也用一个长度为m mm的01 0101串表示第i ii个字符为′ 1 ′ 1′1′代表该药可以治愈第i ii个部位的症状。对于每个病人请你帮小红求出治愈该病人需要开的最少的药数量。输入描述第一行输入两个正整数n , m n,mn,m代表病人数量和症状种类数。接下来的n nn行每行输入一个长度为m mm的01 0101串代表每个病人的症状情况。接下来一行输入一个正整数k kk代表药物的数量。接下来的k kk行每行输入一个长度为m mm的01 0101串代表每个药物可以治愈的症状情况。1 ≤ m ≤ 20 1≤m≤201≤m≤201 ≤ n ≤ 10 4 1≤n≤10^41≤n≤1041 ≤ k ≤ 10 1≤k≤101≤k≤10输出描述输出n nn行每行输出治愈该病人所需的最小药物数量。特殊的如果该病人无法被治愈请输出− 1 -1−1。示例1输入3 4 1000 0101 1011 2 1001 0011输出1 -1 2说明第一个病人开第一种药即可。第二个病人显然是无法治愈的。第三个病人需要同时开第一种和第二种药。解题思路本题是小规模最小集合覆盖问题核心利用药物数量少的特性通过位掩码枚举所有药物子集按子集大小从小到大校验覆盖性找到每个病人所需的最少药物数。1. 问题建模每个病人的症状对应一个需要覆盖的症状集合每种药物对应一个可治愈的症状子集。目标是选出最少的药物使得它们的并集完全覆盖病人的所有症状属于经典的集覆盖问题。由于药物总数 k ≤ 10总子集数量仅为 2^10 1024完全可以通过暴力枚举所有子集得到精确最优解无需使用近似贪心算法。2. 位掩码优化表示因为症状总数 m ≤ 20可将每个病人的症状、每种药物的治愈范围都压缩为一个二进制位掩码二进制第 j 位为 1 表示对应部位有症状/药物可治愈该部位。多个药物的联合治愈效果可通过按位或运算快速计算。覆盖性判断若药物并集与病人症状的按位与等于病人症状本身说明病人所有症状都被覆盖可以治愈。3. 枚举策略按子集大小从小到大遍历为了快速找到最小药物数对每个病人按药物数量 sz 从 1 到 k 依次枚举对每个 sz遍历所有恰好包含 sz 个药物的子集。计算该子集的联合覆盖范围若能覆盖当前病人的所有症状则 sz 就是该病人的最小药数直接输出并进入下一个病人的计算。若所有大小的子集都无法覆盖则输出 -1。4. 特殊边界处理若病人没有任何症状全0掩码无需用药直接输出 0。所有药物的并集仍无法覆盖病人症状时输出 -1。算法总运算量为 n × 2^kn 最大 10^4、k10 时总运算量约 10^7完全适配 1 秒时间限制。总结核心逻辑将症状与药物转化为二进制位掩码利用药物数量少的特性暴力枚举所有子集按子集大小从小到大校验覆盖性得到每个病人的最少用药数。关键操作01串转位掩码、按位或计算联合覆盖、子集大小升序枚举、覆盖性快速校验。效率保障k10 时仅 1024 个子集单次病人查询为常数级开销万级病人可快速处理。代码简要说明数据存储使用bitset20存储每个病人的症状掩码pat和每种药物的覆盖掩码cov适配 m ≤ 20 的规模。读入01字符串时逐位判断若字符为 ‘1’ 则将对应位置位。病人逐个处理若病人症状掩码全空none()直接输出 0跳过后续校验。外层按药物数量sz从 1 到 k 从小到大遍历保证第一个找到的就是最小值。内层枚举所有药物子集掩码mask通过__builtin_popcount统计掩码中 1 的个数筛选出大小恰好为 sz 的子集。覆盖性校验对合法大小的子集遍历所有药物位将选中的药物覆盖掩码做按位或运算得到总覆盖total。若总覆盖包含病人所有症状说明可以治愈立即输出当前 sz标记找到解并跳出所有循环。无解处理遍历完所有子集仍未找到可行方案说明无法治愈输出 -1。输入优化关闭流同步并解绑 tie大幅提升万级病人数据的读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;cinnm;vectorbitset20pat(n);for(ll i0;in;i){string s;cins;for(ll j0;jm;j)if(s[j]1)pat[i].set((int)j);}ll k;cink;vectorbitset20cov(k);for(ll i0;ik;i){string s;cins;for(ll j0;jm;j)if(s[j]1)cov[i].set((int)j);}for(ll q0;qn;q){if(pat[q].none()){cout0endl;continue;}booloktrue;for(ll sz1;szkok;sz){for(ll mask1;mask(1LLk)ok;mask){if(__builtin_popcount((unsigned)mask)!(int)sz)continue;bitset20total;for(ll i0;ik;i)if(maski1LL)total|cov[i];if((totalpat[q])!pat[q])continue;okfalse;coutszendl;}}if(ok)cout-1endl;}return0;}