CF1523D Love-Hate 题解

抽象化题意：

一共有 \(m\) 个元素，给定 \(n\) 个集合，每个集合的元素不超过 \(15\) 个，求出一个元素个数最多的集合 \(S\) 是至少 \(\lceil \dfrac{n}{2} \rceil\) 个集合的子集。

其中$ p $ $ (1 \le n \le 2 \cdot 10^5, 1 \le p \le m \le 60) $

我们先假设 \(limit= \lceil \dfrac{n}{2} \rceil\)

先考虑最基础的暴力，如果我们每次枚举答案集合 \(S\) ，然后再计算出是否有大于等于 \(limit\) 个集合是 \(S\) 的超集，更新答案

计算超集可以通过 \(SOSDP\) ，仍然TLE，先从题目本质入手，它是让我们求一个集合使得是至少 \(\lceil \dfrac{n}{2} \rceil\) 个集合的子集，那么这个答案显然是某 \(\lceil \dfrac{n}{2} \rceil\) 个集合的子集，那如果我们随机任取一个集合，正确答案是它子集的概率就是50%，那我们直接随 \(num\) 次，可以直接让答案错误的概率降到极低，错误的概率就是 \(\dfrac{1}{2^{num}}\) 。

也就是说随机50次的样子，每次对于随机到的集合，通过 \(O(p\times2^p)\) 来计算超集，具体细节就是需要搞个vector来存某位是1的位置就行了。

代码：

#include<bits/stdc++.h>

#define int long long 
 
using namespace std;
 
template<class T>
 
inline T read(){
	T r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r*10)+(c^48),c=getchar();
	return f?-r:r;
}

int n,m,p,limit;
 
int a[200005];
 
bool flag[200005];
 
vector<int>g;
 
inline int idx(char c){
	return c-'0';
}
 
int dp[1000005];

int ans;

mt19937 rd(time(0));
 
inline void work(){
	int pos;
	while(1){
		pos=rd()%n+1;
		if(!flag[pos]){flag[pos]=true;break;}
	}
	g.clear();
	int num=a[pos];
	for(int i=0;i<m;i++){
		if((num>>i)&1)g.emplace_back(i);
	}
	memset(dp,0,sizeof(dp));
	int S=g.size();
	for(int i=1;i<=n;i++){
		int tmp=0;
		for(int j=0;j<S;j++){
			if((a[i]>>g[j])&1)tmp|=(1<<j);
		}
		++dp[tmp];
	}
	for(int i=0;i<S;i++){
		for(int j=0;j<(1ll<<S);j++){
			if(!((j>>i)&1))dp[j]+=dp[j^(1<<i)];
		}
	}
	int res=0;
	for(int i=1;i<(1ll<<S);i++){
		if(dp[i]>=limit){
			if(__builtin_popcountll(res)<__builtin_popcountll(i))res=i;
		}
	}
	int res2=0;
	for(int i=0;i<S;i++){
		if((res>>i)&1)res2|=(1ll<<g[i]);
	}
	if(__builtin_popcountll(res)>__builtin_popcountll(ans))ans=res2;
}
 
signed main(){
	n=read<int>(),m=read<int>(),p=read<int>();
	limit=(n+1)>>1;
	for(int i=1;i<=n;i++){
		char c;
		for(int j=0;j<m;j++){
			cin>>c;
			if(idx(c))a[i]|=(1ll<<j);
		}
	}
	for(int t=1;t<=min(n,50ll);t++)work();
	for(int i=0;i<m;i++)
		((ans>>i)&1)?putchar('1'):putchar('0');
	puts("");
	return 0;
}