hdu3006（状态压缩）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3006

题意：给定一些集合，求这些集合所能组合的集合个数。

分析：这题就是用一个二进制数保存一个集合的元素比如一个集合中有两个元素 1 3 那就用5 （101）表示这个集合

就是用0 1 来表示这个集合中一个数存不存在再比如一个集合有三个元素 1 4 5 就在这几个位子上标为1，那就

用25 （11001）来表示这个集合！在借助于位运算的或（ | ）就可已达到合并集合的目的，比如一个集合（1 4 ）

和一个集合（1 2 3）进行合并那就是（9）1001 | 111（7）=1111 就是15 这样就将重复的部分覆盖了。新的集合就用15来表示！最大就是（11111111111111）2^15-1来表示一个集合！

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 19890907

#define inf 0x3f3f3f3f

#define N 10010

using namespace std;

int vis[<<];

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)>)

    {

        memset(vis,,sizeof(vis));

        for(int i=;i<=n;i++)

        {

            int num,x,res=;

            scanf("%d",&num);

            while(num--)

            {

                scanf("%d",&x);

                res|=<<(x-);

            }

            vis[res]=;

            for(int j=;j<(<<m);j++)

                if(vis[j])vis[j|res]=;

        }

        int ans=;

        for(int i=;i<(<<m);i++)if(vis[i])ans++;

        printf("%d\n",ans);

    }

}

秒客网

hdu3006（状态压缩）

相关文章