[USACO 2006 Ope B]Cow Pizza

Line 1: Two space-separated integers: T and N
Lines 2..N+1: Each line describes a constraint using space-separated
The first integer is the number of ingredients in constraint, Z (1 <= Z <= T). The subsequent Z integers (which are unique) list the ingredient(s) whose combination a pizza from consideration for the cows.

C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 480K, 提交时间: 2019-06-23 20:25:02

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans,l[55];
int main(){
	int t,n,z,a;
	scanf("%d%d",&t,&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&z);
		while(z--){
			scanf("%d",&a);
			l[i]|=1<<(a-1);
		}
	}
	for(int s=0;s<(1<<t);s++){
		int f=1;
		for(int i=1;f&&i<=n;i++)
		if((s&l[i])==l[i])f=0;
		if(f)ans++;
	}
	printf("%d\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 15ms, 内存消耗: 632K, 提交时间: 2019-06-26 17:36:53

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int a[600];
int main() 
{
	int n,m;
	cin>>n>>m;
	int q,w;
	for(int i=1;i<=m;i++)
	{
		cin>>q;
		for(int j=1;j<=q;j++)
		{
			cin>>w;
			a[i]|=(1<<w-1);
		}
	}
	int s=0;
	for(int i=0;i<(1<<n);i++){
	
	for(int j=1;j<=m;j++)
	{
		if((a[j]&i)==a[j])
		{
		s++;
		break;
	}
		
	}
	}
	cout<<(1<<n)-s<<endl;
}

详情