💡题解思路

✅ 本质：

从 $N$ 头奶牛中选择一个最大子集，使得它们携带的疾病种类数不超过 $K$。

✅ 关键观察：

疾病种类 $D \leq 15$，很小；

可以枚举所有疾病的子集（最多 $2^D = 32768$ 个）；

枚举所有疾病集合中，包含疾病种类 $\leq K$ 的集合；

对于每一个疾病集合 mask，计算有哪些奶牛的疾病集合是它的子集，这些奶牛可以一起被挤奶；

取所有满足条件的最大奶牛数。

✅ 技术细节：

每头奶牛的疾病集合用一个 int 位掩码表示；

枚举所有 $K$ 位以内的疾病集合 mask；

对所有奶牛判断其疾病集合是否是 mask 的子集；

记录满足条件的最大数量。

⌛复杂度分析

枚举的疾病集合最多 $2^{15} = 32768$；

每个集合判断奶牛是否满足 $O(N)$；

总复杂度：$O(2^D \times N)$，最多 $32,768 \times 1,000 = 32,768,000$，完全可接受。

代码实现

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int state[1<<15],ans,n,m,k,ed;

int main()
{
	scanf("%d%d%d",&n,&m,&k),ed=(1<<(m+1))-1;
	for(int i=1;i<=n;i++)
	{
		int l;scanf("%d",&l);
		while(l--)
		{
			int x;scanf("%d",&x);
			state[i]|=(1<<x);
		}
	}
	for(int i=0;i<=ed;i++)
	{
		int sum=0;
		for(int j=i;j;j-=j&(-j)) sum++;
		if(sum>k) continue;
		sum=0;
		for(int j=1;j<=n;j++) if((state[j]&i)==state[j]) sum++;
		ans=max(ans,sum);
		if(ans==7) {cout<<i<<"!\n";break;}
	}
	cout<<ans;
	return 0;
}