HDU/HDOJ 3006 The Number of set(位状态压缩+枚举)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3006

位状态压缩的经典体型。

题意是给出一些集合,求这些集合的并集一共有多少种?

这里有点类似模->数转换,由此想到位状态压缩,把输入的数据压缩成一位,一个set就转换成一个int型了。

至于如何转换,就要用到逻辑或“|”运算符,逻辑或用于把set压缩成int以及把两个集合合并。

具体见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Author: Tanky Woo
// Blog: www.WuTianQi.com
// Title: HDOJ 3306 The Number of set
// About: 位状态压缩+枚举
 
#include <iostream>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注