ACM-ICPC 2017 南宁赛区网络预赛 M Frequent Subsets Problem 【状态压缩+暴力】

本文主要是介绍ACM-ICPC 2017 南宁赛区网络预赛 M Frequent Subsets Problem 【状态压缩+暴力】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

•  1000ms
•  131072K

The frequent subset problem is defined as follows. Suppose U={1, 2,…,N} is the universe, and S1​, S2​,…,SM​ are M sets over U. Given a positive constant α, 0<α≤1, a subset B (B≠0) is α-frequent if it is contained in at least αM sets of S1​, S2​,…,SM​, i.e. {i:B⊆Si​}∣≥αM. The frequent subset problem is to find all the subsets that are α-frequent. For example, let U={1,2,3,4,5}, M=3, α=0.5, and S1​={1,5}, S2​={1,2,5}, S3​={1,3,4}. Then there are 3 α-frequent subsets of U, which are {1},{5} and{1,5}.

Input Format

The first line contains two numbers N and α, where N is a positive integers, and α is a floating-point number between 0 and 1. Each of the subsequent lines contains a set which consists of a sequence of positive integers separated by blanks, i.e., line i + 1i+1 contains Si​, 1≤i≤M . Your program should be able to handle N up to 20 and M up to 50.

Output Format

The number of α-frequent subsets.

样例输入

15 0.4
1 8 14 4 13 2
3 7 11 6
10 8 4 2
9 3 12 7 15 2
8 3 2 4 5

样例输出

11

题目来源

2017 ACM-ICPC 亚洲区（南宁赛区）网络赛

题目大意：数字N表示全集为1，2，...，N。给你M个集合，问有多少个子集满足至少有a*M个集合包含它。

题解：状态压缩，用20位二进制表示每个集合中1到N这些数是否出现,如果出现相应位置为1否则为0，比如一个集合为{1，2}则表示为00000000000000000011(只有第一位和第二位为1)，然后枚举每个子集，判断即可

AC的C++代码：

#include<iostream>
#include<cmath>using namespace std;int main()
{int n,k=0,x,res=0,s[55]={0};double a;char c;scanf("%d%lf",&n,&a);while(~scanf("%d%c",&x,&c)){s[k]+=(1<<(x-1));if(c=='\n')k++;}int num=ceil(k*a);//向上取整 for(int i=1;i<(1<<n);i++){int cnt=0;for(int j=0;j<k;j++)if((i&s[j])==i)//&的优先级比==小，因此必须有括号 cnt++;if(cnt>=num)res++;}printf("%d\n",res);return 0;
}

 

这篇关于ACM-ICPC 2017 南宁赛区网络预赛 M Frequent Subsets Problem 【状态压缩+暴力】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---