2017ICPC 南宁网络赛M Frequent Subsets Problem

样例输入

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

题意：给你一个n，频率a以及m个集合，要求是求出在m个集合中出现频率大于等于a的子集个数，如样例中就是在两个及以上的集合中出现过的子集，分别是{8},{4},{3},{2},{7},{8,4},{8,2},{2,4},{8,4,2},{2,3},{3,7}。
思路：n最大是20，1<<20 大概比1e6大一点，所以暴力不会超时。总共有2的20次方种状态，所以要进行状压。状压的特点就运用位运算，假设用state表示当前集合状态，(state|1<<(i-1))就是把第i个数加进当前集合，(state&1<<(i-1))表示第i个数在不在当前集合，(state&k)==k表示 state 和k是同一种状态。

#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define N 1<<20
using namespace std;
int s[105],ans;
int main()
{
int n ,m,k;
double a;
memset(s,0,sizeof(s));
m=1;
ans=0;
scanf("%d%lf",&n,&a);
int x;
char ch;
while(~scanf("%d%c",&x,&ch))
{
s[m]=s[m]|(1<<(x-1));
if(ch=='n')
m++;
}
k=ceil(m*a);
for(int i=1;i<(1<<n);i++)
{
int sum=0;
for(int j=1;j<=m;j++)
{
if((s[j]&i)==i)
sum++;
}
if(sum>=k) ans++;
}
printf("%dn",ans);
return 0;
}

最后

以上就是执着航空为你收集整理的2017ICPC 南宁网络赛M Frequent Subsets Problem的全部内容，希望文章能够帮你解决2017ICPC 南宁网络赛M Frequent Subsets Problem所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。