hdu 3006 枚举集合可以产生的所有并集的集合

本文主要是介绍hdu 3006 枚举集合可以产生的所有并集的集合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=3006

刚买的CHERRY键盘 手感真好 可惜不习惯 写代码老是打错，一个题写了一上午，都是各种按错键DEBUG.....

开始想的是DFS  发现好像不行

然后想的是两重循环可以枚举所有的2个集合的并集，3重循环可以枚举所有3个集合的并集，那么n个子集貌似需要n重循环，NP问题啊，，，，，

做法还是从小的数去模拟，因为只有14个，所以状压存储

如第一个例子

四个子集1,2,3,4

二进制0001 0010 0011 0100

第一个与其他三个或操作  得到0001 0010 0011 0100 0011  0101....

然后第二个数和新的数异或

代码中第二重循环 i+1开始，放重复，其实省不了多少时间 o(╯□╰)o

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;#define IN(s) freopen(s,"r",stdin)
#define CL(a,b) memset(a,b,sizeof(a))const int MAXN = 1<<15;
int vis[MAXN],ans[MAXN];int main()
{//IN("hdu3006.txt");int n,m;int k;while(~scanf("%d%d",&n,&m)){CL(vis,0);int cnt=0;for(int j=0;j<n;j++){scanf("%d",&k);int t=0,a=0;for(int i=0;i<k;i++){scanf("%d",&t);a|=1<<(t-1);}if(!vis[a]){vis[a]=1;ans[cnt++]=a;}}int ct=cnt;for(int i=0;i<ct;i++){int s=ans[i];for(int j=i+1;j<cnt;j++){if(!vis[(s|ans[j])] && i!=j){vis[s|ans[j]]=1;ans[cnt++]=s|ans[j];}}}printf("%d\n",cnt);}return 0;
}

这篇关于hdu 3006 枚举集合可以产生的所有并集的集合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---