细菌(disease) (位运算)(状态压缩)
2024-09-27 02:11:04
细菌(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 ;
}
最新文章
- js学习之类型识别
- !important使用
- Centos 7 安装jdk 配置环境变量
- 在docker 中搭建gitlab环境
- jar包制作
- iOS - UIAlertView
- 【环境】openSUSE安装记录 - 古董本上的windows 7和opensuse双系统
- 异常:Caused by: java.lang.NoClassDefFoundError: Could not initialize class net.sf.log4jdbc.Properties
- bzoj 2588 Spoj 10628. Count on a tree(主席树)
- iOS调用系统通讯录获取姓名电话号码(转)
- mysql 5.5 win7安装最后一步总是停止响应
- [leetcode] 406. Queue Reconstruction by Height
- 关于XMLEncoder和XMLDecoder
- redis(Remote Dictionary Server)
- zeromq随笔
- E. Change-free
- Spring框架学习笔记(2)——IOC&;DI
- c语言static关键字的理解
- day15-集合
- Luogu 1970 NOIP2013 花匠 (贪心)