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)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[]; int main()
{
memset(a,,sizeof(a));
int N,M=,t,ans=;
double r;
char c;
cin>>N>>r;
while(scanf("%d%c",&t,&c)!=EOF)
{
a[M]+=<<(t-);
if(c=='\n') M++;
}
int num=ceil(r*M);
for(int i=;i<=(<<N);i++){
int sum=;
for(int j=;j<M;j++){
if(i==(i&a[j])) sum++;
}
if(sum>=num) ans++;
}
cout<<ans<<endl;
return ;
}
参考博客：