题目描述

有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

解答

要求指定约束下的组合数,使用位标记表示某个元素取或不取,例如1011(7)表示取134的组合,通过位标记表示约束,再通过位运算判断是否违反约束,最终统计出组合数。
#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;
}

来源:Hpatron