Frequent Subsets Problem

The frequent subset problem is defined as follows. Suppose $S1S_{1}S1, S2S_{2}S2,…ldots…,SMS_{M}SM are MMM sets over UUU. Given a positive constant αalphaα, 0<α≤10<alpha leq 10<α≤1, a subset BBB (B≠0B eq 0B≠0) is α-frequent if it is contained in at least αMalpha MαM sets of S1S_{1}S1, S2S_{2}S2,…ldots…,SMS_{M}SM, i.e. ∣{i:B⊆Si}∣≥αMleft | left { i:Bsubseteq S_{i} ight } ight | geq alpha M∣{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}U={1, 2,3,4,5}U={1,2,3,4,5}, M=3M=3M=3, α=0.5alpha =0.5α=0.5, and S1={1,5}S_{1}={1, 5}S1={1,5}, S2={1,2,5}S_{2}={1,2,5}S2={1,2,5}, S3={1,3,4}S_{3}={1,3,4}S3={1,3,4}. Then there are 333 α-frequent subsets of UUU, which are {1}{1}{1},{5}{5}{5} and {1,5}{1,5}{1,5}.$

Input Format

The first line contains two numbers $SiS_{i}Si, 1≤i≤M1 le i le M1≤i≤M . Your program should be able to handle NNN up to 202020 and MMM up to 505050.$

Output Format

The number of

样例输入

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

样例输出

题目来源

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

求在m个集合中出现次数大于a*m的子集数量。n不大与20 最大1<<20 不会超时，直接暴力可以做。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 110;
 5 int a[N];
 6 int main() {
 7     int n, num = 0, m = 0;
 8     double aa;
 9     char c;
10     scanf("%d %lf", &n, &aa);
11     getchar();
12     while((c = getchar()) != EOF) {
13         int ans = c - '0';
14         while((c = getchar()) != '
') {
15             if(c >= '0' && c <= '9') {
16                 ans = ans * 10 + c - '0';
17             }else {
18                 a[m] += 1 << (ans - 1);
19                 ans = 0;
20             }
21         }
22         a[m] += 1 << (ans - 1);
23         m ++;
24     }
25     int ma = ceil(aa*m);
26     int cnt = 0;
27     for(int i = 1; i < (1<<n); i ++) {
28         int num = 0;
29         for(int j = 0; j < m; j ++) {
30             if((i & a[j]) == i) num ++;
31         }
32         if(num >= ma) cnt++;
33     }
34     printf("%d
",cnt);
35     return 0;
36 }