题意
有\(n\)个集合与和一个有\(m\)个元素的全集\(U\)，每个集合都是\(U\)的子集，且每个集合大小不超过\(p\)，求一个最大的\(U\)的子集\(A\)，使得\(A\)至少是\(n\)个集合中\(\lceil \frac{n}{2}\rceil\)个集合的子集。
\(1\le n\le 2\times10^5,1\le p\le m\le 60,1\le p\le 15\)
题解
#include <bits/stdc++.h>
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=3e5+10,INF=1<<30;
int n,m,p=0,c[N],aa[N],res[62];
char s[75];
int pc[(1<<15)+10];
void fwtand(ll *a,int n,int typ){
for(int mid=1;mid<n;mid<<=1){
for(int r=(mid<<1),j=0;j<n;j+=r){
for(int i=0;i<mid;i++){
a[i+j]=(a[i+j]+typ*a[i+j+mid]);
}
}
}
}
ll ov[N];
ll a[(1<<15)+10];
unsigned sd=chrono::system_clock::now().time_since_epoch().count();
mt19937 rndnum(sd);
int rnd(int n){
unsigned res=rndnum()%n+1;
return res;
}
int vis[N];
void f1(){
for(int i=1,l=(1<<15);i<l;i++)pc[i]=pc[i>>1]+(i&1);
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++){
//aa[i]=i;
vis[i]=0;
scanf("%s",s+1);
for(int j=1;j<=m;j++){
if(s[j]==‘1‘){ov[i]|=(1ll<<(j-1));}
}
}
int ans=0;
for(int o=1;o<=min(200,n);o++){
int u=rnd(n);
while(vis[u]){
u=rnd(n);
//assert(u<=n&&u>=1);
}
vis[u]=1;
ll na=ov[u];p=0;
for(int i=1;i<=m;i++){
if((1ll<<(i-1))&na){c[++p]=i;}
}
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++){
ll y=(na&ov[i]),z=0;
for(int j=1;j<=p;j++){
if((1ll<<(c[j]-1))&y){
z|=(1<<(j-1));
}
}
++a[z];
}
int l=(1<<p);
fwtand(a,l,1);
for(int i=0;i<l;i++)if(a[i]*2>=n&&pc[i]>ans){
ans=pc[i];
memset(res,0,sizeof(res));
for(int j=1;j<=p;j++)if(i&(1<<(j-1))){
res[c[j]]=1;
}
}
}
for(int i=1;i<=m;i++){printf("%d",res[i]);}
}
int main(){
//int t;
//scanf("%d",&t);
//while(t--)
f1();
return 0;
}
/*
3 4 3
1000
0110
1001
*/