首页 > 代码库 > hdu3006（状态压缩）
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 10010using namespace std;int vis[1<<15];int main(){ int n,m; while(scanf("%d%d",&n,&m)>0) { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { int num,x,res=0; scanf("%d",&num); while(num--) { scanf("%d",&x); res|=1<<(x-1); } vis[res]=1; for(int j=0;j<(1<<m);j++) if(vis[j])vis[j|res]=1; } int ans=0; for(int i=0;i<(1<<m);i++)if(vis[i])ans++; printf("%d\n",ans); }}
hdu3006（状态压缩）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。