HD 3006 The Number of set(位运算)

不熟悉BestCoder的比赛？看看这里—>《BestCoder用户手册》下载链接

The Number of set Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1098    Accepted Submission(s): 685 Problem Description Given you n sets.All positive integers in sets are not less than 1 and not greater than m.If use these sets to combinate the new set,how many different new set you can get.The given sets can not be broken.   Input There are several cases.For each case,the first line contains two positive integer n and m(1<=n<=100,1<=m<=14).Then the following n lines describe the n sets.These lines each contains k+1 positive integer,the first which is k,then k integers are given. The input is end by EOF.   Output For each case,the output contain only one integer,the number of the different sets you get.   Sample Input 4 4 1 1 1 2 1 3 1 4 2 4 3 1 2 3 4 1 2 3 4 Sample Output 15 2

本题目将每组数据的值通过二进制代码的位值表示出来，在达到题目要求的组合时，用按位或运算结合起来，不同数据结合后数值是不同的，当数值相等时，就是再次把1赋给a[i],对题目无影响；
           

在做右移运算时，右移0位是本身，所以当所表示的值为2时，应该是1<<k-1,k=2;
           

#include<stdio.h>
#include<string.h> 
int main()
{
	int n,m,t,b,i,k,s,a[1<<15];//<span style="font-family: Arial, Helvetica, sans-serif;">a[1<<15]并不等价于a[15]而是a[2^15]</span>

	while(scanf("%d%d",&n,&m)!=EOF)
	{
		s=0;
		memset(a,0,sizeof(a));
		while(n--)
		{
			b=0;
			scanf("%d",&t);
			while(t--)
			{
				scanf("%d",&k);
				b=b|(1<<(k-1)); //如此预算后b的值会很大 
			}
			a[b]=1;
			for(i=0;i<=(1<<14);i++) //1=<m<=14故定义数组应大于（1<<14）
			{
				if(a[i])
					a[i|b]=1;
			}
		}
		for(i=0;i<=1<<14;i++)
		{
			if(a[i])
				s++;
		}
		printf("%d\n",s);
	}
	return 0;
}