细菌(disease)
时间限制: 1 Sec 内存限制: 64 MB
提交: 9 解决: 5
[提交][状态][讨论版]
题目描述
近期,农场出现了D(1≤D≤15)种细菌。John要从他的N(1≤N≤1000)头奶牛中尽可能多地选些产奶,但是如果选中的奶牛携带了超过K(1≤K≤D)种不同细菌,所生产的奶就不合格。请你帮助John计算出最多可以选择多少头奶牛。
输入
第1行:三个整数N,D,K。
下面N行:第i行表示一头牛所携带的细菌情况。第一个整数di表示这头牛所携带的细菌种类数,后面di个整数表示这些细菌的各自种类标号。
输出
一个数M,最大可选奶牛数。
样例输入
6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1
样例输出
5
提示
样例说明:选择l,2,3,5,6头奶牛,只有1#和2#两种细菌。
【分析】看的别人的题解,第一次见这种做法,位运算,很叼的样子。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define inf 0x3f3f3f3f
#define mod 1000000007
typedef long long ll;
using namespace std;
const int N=;
int n,k,d,m,t;
int a[N],cnt[]; int fun(int x)
{
int c=;
while(x)
{
if(x&)c++;x>>=;
}return c;
}
int main() {
memset(a,,sizeof(a));
memset(cnt,,sizeof(cnt));
cin>>n>>d>>k; int ans=;
for(int i=;i<n;i++)
{
cin>>t;
for(int j=;j<t;j++)
{cin>>m;
a[i]+=pow(,m-);
}
} for(int i=;i<=pow(,d);i++)
{
if(fun(i)>k)continue;
for(int j=;j<n;j++)
{
if((i|a[j])==i)cnt[i]++;
}
ans=max(ans,cnt[i]);
} cout<<ans<<endl;
return ;
}