题解 | 奶牛披萨-牛客假日团队赛3A题

题目描述

有T种馅料，但有些馅料不能被放在一起。求选出一些馅料的方案数是多少。
文件输入第一行为两个整数 和，表示接下来行会有个限制。
接下来行，每行的第一个数表示接下来数的个数：，表示任意一种陷料中这种馅料不能同时出现。
如果，则表示 这种陷料在任何一种组合中都不得出现。
如果 表示 三种馅料不能在任何一种组合中出现。

Line 1: Two space-separated integers: and

Lines : Each line describes a constraint using space-separated

The first integer is the number of ingredients in constraint, . The subsequent Z integers (which are unique) list the ingredient(s) whose combination a pizza from consideration for the cows.

Line 1: A single integer that is the total number of pizzas that can be created using the number of ingredients and constraints.

示例1

6 5
1 1
2 4 2
3 3 2 6
1 5
3 3 4 6

10

解答

#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<<"\n";
    return 0;
}