2014
02-27

# The Number of set

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.

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.

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.

4 4
1 1
1 2
1 3
1 4
2 4
3 1 2 3
4 1 2 3 4

15
2

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
int m,n,k,a;
int s[1<<15];            //2的15次方
while(cin>>n>>m)
{
int ans=0;
memset(s,0,sizeof(s));
while(n--)
{
int set=0;
cin>>k;
while(k--)
{
cin>>a;
set=set|(1<<(a-1));
}
s[set]=1;
for(int j=0;j<=(1<<14);j++)
{
if(s[j])  s[set|j]=1;
}

}
for(int i=0;i<=1<<14;i++)
{
if(s[i])
ans++;
}
cout<<ans<<endl;
}
return 0;
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。