hdu3006 状态压缩+位运算+hash（小想法题）

题意：
       给了n个集合，问你这n个集合可以组合出多少种集合，可以自己，也可以两个，也可以三个....也可以n个集合组在一起。

思路：

      是个小想法题目，要用到二进制压缩，位运算，还有hash，这4样加起来说明这个题目真的很不错，不废话，首先对于每个集合有k个元素，每个元素都是不大于14的，那么我们可以二进制压缩，把每个集合压缩成一个二进制数，压缩过程设计到位运算对于每个集合
tmp = 0;
for(i ,1 - k) scanf(num) ,tmp = tmp | (1 << (num - 1));
hash[tmp] = 1;标记上当前的这个集合是可以得到的。
这样最后的这个tmp就是当前的这个集合压缩后的数，然后我们在枚举之前的所有可能状态，得到新的可能状态（其实就是简单dp）

for(i = 1 ;i < 1 << 14 ;i ++) if(hash[i]) hash[i|tmp] = 1; 之前的可能情况加上当

前的可能情况也是可能情况。最后在统计下可能情况的个数就ok了，
for(i = 1 ;i < 1 << 14 ;i ++) if(hash[i]) ans++;

做这个题目的时候sb了，开了个 hash[1<<13+1] 哎！ 1<<13+1 != 1 << 14 - 1.

#include<stdio.h> #include<string.h> int hash[1 << 14];int main () {int n ,m ,i ,j ,k ,num ,tmp ,ans;while(~scanf("%d %d" ,&n ,&m)){memset(hash ,0 ,sizeof(hash));for(i = 1 ;i <= n ;i ++){scanf("%d" ,&k);tmp = 0;for(j = 1 ;j <= k ;j ++)scanf("%d" ,&num) ,tmp = tmp | (1 << (num - 1));hash[tmp] = 1;for(j = 0 ;j < 1 << 14 ;j ++)if(hash[j]) hash[tmp | j] = 1;}ans = 0;for(i = 0 ;i < 1 << 14 ;i ++)if(hash[i]) ans ++;printf("%d\n" ,ans);}return 0; }

总结

以上是生活随笔为你收集整理的hdu3006 状态压缩+位运算+hash（小想法题）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。