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

题目链接

题目翻译:
给出一个数n,和一个浮点数a,数n代表全集U = {1,2,...,n},然后给出
M个U的子集,如果一个集合B(是U的子集),M个集合中有至少M*a个集合包含B,
则B这个集合就是一个满足条件的集合,统计U的子集中B这种集合的个数。

对于N个数的集合,其子集,可以从N个里面挑1个,挑2个,。。。挑N个数构成。
C(n,0)+ C(n,1) + C(n,2) + C(n,3) + ..... + C(n,n) = (1+1)^n = 2^n
N个数子集共有2^n种状态,其中每一个数都代表一个状态,意思就是代表一个子集。
对于输入的M个集合。集合的状态就是2^(num-1)的和。
为何这样?
加入现有一个集合:
1 3 6 10
把它算成 2^(1-1) + 2^(3-1) + 2^(6-1) + 2^(10-1)
这个数字可以用2进制表示:
num(数字): 10 9
8 7 6 5 4
3 2 1
binary bit(二进制位): 1 0 0 0 1 0 0 1 0 1
power(对应的权值): 2^9 2^8 2^7 2^6 2^5 2^4 2^3 2^2 2^1 2^0
对于每个状态,是一个数,它也是一个二进制串,二进制串中为1的位置,代表了
某个数字存在与集合M,当每个数与集合M进行与运算的时候,可以求出同为1的
二进制位,得出的数与当前这个相同,则说明当前数代表的状态是集合M的子集。

AC代码:


#include <iostream>  
#include <stdio.h>  
#include <math.h>  
#include <string.h>   
using namespace std;  
char str[1000];  
int M[55];  
int main()  
{  
    int n,m;  
    double a;  
    scanf("%d %lf ",&n,&a);  
    memset(M,0,sizeof(M));  
    m = 0;  
    while(gets(str))  
    {  
        int num = 0;  
        int len = strlen(str);  
        for(int i = 0; i < len; i++)  
        {  
            if(str[i]==' ')  
            {  
                M[m] = M[m] + (1<<(num-1));  
                num = 0;  
            }  
            else  
            {  
                num = num*10 + str[i]-'0';  
            }  
        }  
        M[m++] += (1<<(num-1));  
    }  
    int temp = ceil(m*a);  
    int state = (1<<n);  
    int ans = 0;  
    for(int i = 1; i <= state; i++)  
    {  
        int sum = 0;  
        for(int j = 0; j < m; j++)  
        {  
            if((i&M[j]) == i)  
                sum++;  
        }  
        if(sum >= temp)  
            ans++;  
    }  
    printf("%d
",ans);  
    return 0;  
}  
原文地址:https://www.cnblogs.com/cmmdc/p/7610768.html