CF 1523D - Love-Hate

• 考虑枚举每个人，选择它的集合的子集作为方案。

  这样只有本质不同的 \(2^p\) 个集合，枚举子集或者 FMT 每次可以做到 \(O(3^p/p2^p)\)。

• 但是人太多了怎么办？注意到每个人都有 \(\frac {1}{2}\) 的概率出现在方案中，连续 \(k\) 个人都不在方案中的概率为 \({\frac{1}{2}}^k\)。

  那么将顺序打乱，只用选 \(40\) 个人就可以取得非常高的正确率。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int n, mx, m, a[64], b[1<<15], c[1<<15], tot;

LL ans, v[N];

char s[N];

void check_(LL x) {
	tot = 0;
	
	for (int i = 0; i < m; i++)	
		if (x&(1ll<<i))
			a[tot++] = i;
	
	for (int i = 0; i < (1<<tot); i++)	
		b[i] = 0, c[i] = c[i>>1] + (i&1);
			
	for (int i = 1; i <= n; i++) {
		int cur = 0;
		
		for (int j = 0; j < tot; j++)
			if (v[i]&(1ll<<a[j]))
				cur += 1<<j;
		
		b[cur]++;
	}
	
	for (int i = 0; i < tot; i++)
		for (int j = 0; j < (1<<tot); j += 2ll<<i)
			for (int k = 0; k < (1<<i); k++)
				b[j + k] += b[j + k + (1<<i)];
	
	for (int i = (1<<tot) - 1; i; i--)
		if (b[i]*2 >= n && c[i] > mx) {
			mx = c[i], ans = 0;
			
			for (int j = 0; j < tot; j++)
				if (i&(1<<j))	
					ans |= 1ll<<a[j];
		}
}

int main() {
	srand(time(0));
	
	scanf("%d%d%*d", &n, &m);
	
	for (int i = 1; i <= n; i++) {
		scanf("%s", s);
		
		for (int j = 0; j < m; j++)
			if (s[j] == ‘1‘)
				v[i] |= 1ll<<j;
	}
	
	random_shuffle(v + 1, v + n + 1);
	
	for (int i = 1; i <= min(32, n); i++)
		check_(v[i]);
	
	for (int i = 0; i < m; i++)
		printf("%d", (ans&(1ll<<i)) > 0);
} 

CF 1523D - Love-Hate

原文：https://www.cnblogs.com/iqx37f/p/14833020.html