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;
}