首页 > 代码库 > 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 枚举集合可以产生的所有并集的集合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。