D—医生

本人是小白，赛时D题卡了，赛后看的@Silencer76大佬的题解，可以去看他的原题解（在吐槽区），本小白只是将他的代码转成c++（AI转的，小白不懂Python)，花了好久才理解。大佬勿喷 （ ┭┮﹏┭┮ ）

代码写了非常详细的注释，面向像我一样的小白。

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

int t,n,m,k;
map<string, int> d;
void check(vector<bool>& b, vector<string>& c)
{
	string s(m,'0');//s用来记录这种药品搭配可以治愈什么类型的疾病
	int cnt=0;//用药数量
	for(int i=0;i<k;i++)
	{
		if(b[i])//如果选了第i种药
		{
			cnt++;//用药数量+1
			for(int j=0;j<m;j++)//遍历这种药物，找出这种药物可以治愈哪些部位的疾病
			{
				if(c[i][j]=='1')//c存的是药
					s[j]='1';//第j位置的病可以治愈
			}
		}
		if(d.find(s)!=d.end())//如果之前已经有了相同的 能够治愈的部位的方案，取最小
			d[s]=min(d[s],cnt);
		else
			d[s]=cnt;//没有就记录
	}
}

void dfs(vector<bool>& b, vector<string>& c, int x)
{
	if(x==k)//遍历完了所有药，检查这种药品的搭配可以治愈哪些部位的疾病
	{
		check(b,c);
		return ;
	}
	else
	{
		b[x]=true;//选第x种药
		dfs(b,c,x+1);
		b[x]=false;//不选第x种药
		dfs(b,c,x+1);
	}
}
void solve(){
	cin>>n>>m;
	vector<string> a(n);
	for(int i=0;i<n;i++)
		cin>>a[i];
	cin>>k;
	vector<string> c(k);//c存药
	vector<bool> b(k,false);//标记第 i 种药是否选择
	for(int i=0;i<k;i++)
		cin>>c[i];
	
	dfs(b,c,0);//dfs搜索这 K 种药物可以有多少种搭配方案，得出每种搭配方案对应的 所能治愈的部位 以及 最小的用药数量
	
	for(int i=0;i<n;i++)
	{
		int ans=100;
		for(auto it:d)//从d里面取元素，看看这些不同的搭配是否可以治愈第 i 个人的所有部位的疾病
		{
			string temp=it.first;//这种搭配可以治愈的部位（1表示可以治愈，0表示不行）
			bool sign=1;
			int cnt=it.second;//用药数量
			for(int j=0;j<m;j++)
			{
				if(a[i][j]=='1' && temp[j]=='0')//如果这个人的第 j 个部位有病，但是这种搭配不能治愈这个部位（0表示这种方案不能治愈的部位），
				{								//那么这种搭配方案就不行，直接退出循环，看看下一种搭配方案是否可行
					sign=0;
					break;
				}
			}
			if(sign)//取最小值
				ans=min(ans,cnt);
		}
		if(ans==100)//ans没有被更改过，就说明所有的搭配都不能治愈这个人（可怜┭┮﹏┭┮）
			cout<<-1<<"\n";
		else
			cout<<ans<<"\n";
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}