这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3006
位状态压缩的经典体型。
题意是给出一些集合，求这些集合的并集一共有多少种？
这里有点类似模->数转换，由此想到位状态压缩，把输入的数据压缩成一位，一个set就转换成一个int型了。
至于如何转换，就要用到逻辑或“|”运算符，逻辑或用于把set压缩成int以及把两个集合合并。
具体见代码：
// Author: Tanky Woo
// Blog: www.WuTianQi.com
// Title: HDOJ 3306 The Number of set
// About: 位状态压缩+枚举
#include
using namespace std;
int n, m, k;
int arr[ 1<<16 ];
int main()
{
//freopen("input.txt", "r", stdin);
while(cin >> n >> m)
{
memset(arr, 0, sizeof(arr));
int ans = 0; // 记录set种数
int tmp, res; // tmp - 保存输入数据 res - 保存一个set状态压缩后的值
for(int i=1; i<=n; ++i)
{
cin >> k;
res = 0;
for(int j=1; j<=k; ++j)
{
cin >> tmp;
res |= (1 << (tmp-1));
}
arr[res] = 1;
//cout << "cnt = " << cnt << endl;
for(int j=0; j<=(1<<15); ++j)
if(arr[j])
arr[j|res] = 1;
}
for(int i=1; i<=(1<<15); ++i)
if(arr[i])
++ans;
cout << ans << endl;
}
return 0;
}