# 2017 ACM-ICPC 亚洲区(南宁赛区)网络赛M题

xiaoxiao2021-02-28  14

The frequent subset problem is defined as follows. Suppose UU={1, 2,\ldots…,N} is the universe, and S_{1}S ​1 ​​ , S_{2}S ​2 ​​ ,\ldots…,S_{M}S ​M ​​ are MM sets over UU. Given a positive constant \alphaα, 0<\alpha \leq 10<α≤1, a subset BB (B \neq 0B≠0) is α-frequent if it is contained in at least \alpha MαM sets of S_{1}S ​1 ​​ , S_{2}S ​2 ​​ ,\ldots…,S_{M}S ​M ​​ , i.e. \left | \left { i:B\subseteq S_{i} \right } \right | \geq \alpha M∣{i:B⊆S ​i ​​ }∣≥αM. The frequent subset problem is to find all the subsets that are α-frequent. For example, let U={1, 2,3,4,5}U={1,2,3,4,5}, M=3M=3, \alpha =0.5α=0.5, and S_{1}={1, 5}S ​1 ​​ ={1,5}, S_{2}={1,2,5}S ​2 ​​ ={1,2,5}, S_{3}={1,3,4}S ​3 ​​ ={1,3,4}. Then there are 33 α-frequent subsets of UU, which are {1}{1},{5}{5} and {1,5}{1,5}.

Input Format

The first line contains two numbers NN and \alphaα, where NN is a positive integers, and \alphaα 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 S_{i}S ​i ​​ , 1 \le i \le M1≤i≤M . Your program should be able to handle NN up to 2020 and MM up to 5050.

Output Format

The number of \alphaα-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

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int a; int main() { memset(a,0,sizeof a); int m=0,n; double p; scanf("%d%lf",&n,&p); int num; char ch; while(scanf("%d%c",&num,&ch)!=EOF) { a[m]+=(1<<(num-1)); if(ch=='\n')m++; } int ans=0; int sta=ceil(m*p); for(int i=1;i<(1<<n);i++) { int sum=0; for(int j=0;j<m;j++) { if((i&a[j])==i)sum++; } if(sum>=sta)ans++; } cout<<ans<<endl; return 0; }