2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 M. Frequent Subsets Problem【状态压缩】

2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 M. Frequent Subsets Problem

题意：给定N和α还有M个U={1,2,3,...N}的子集，求子集X个数，X满足：X是U的子集且出现在M个子集中的次数>=α*M。

题解：因为N<=20，所以U的子集个数最大不过2^20。所以采用二进制把每个子集M映射压缩成一个数，比如：

　　　　　　M={1,4,8，10}==>2^(1-0)+2^(4-1)+2^(8-1)+2^(10-1)=1+8+128+512=649（映射记为f,即f(M)=649）

那么只要子集X是M的子集，就会有f(X)=f(X)&f(M)，因为映射f就相当于把集合的每位映射到对应的二进制位上去，如果X是M的子集，必然有前面式子成立。

所以只要枚举U的子集X，再循环M判断X是否在其中，累计X出现的次数判断即可。小细节注意U={1,2..N}不包括0，所以从1开始枚举。时间复杂度O(2^N*M)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int a[55];
 8 
 9 int main()
10 {
11     memset(a,0,sizeof(a));
12     int N,M=0,t,ans=0;
13     double r;
14     char c;
15     cin>>N>>r;
16     while(scanf("%d%c",&t,&c)!=EOF)
17     {
18         a[M]+=1<<(t-1);
19         if(c=='
') M++;
20     }
21     int num=ceil(r*M);
22     for(int i=1;i<=(2<<N);i++){
23         int sum=0;
24         for(int j=0;j<M;j++){
25             if(i==(i&a[j])) sum++;
26         }
27         if(sum>=num) ans++;
28     }
29     cout<<ans<<endl;
30     return 0;
31 }

参考博客：

【1】：http://blog.csdn.net/wyxeainn/article/details/78089281

【2】：http://blog.csdn.net/mitsuha_/article/details/78078306