Educational Codeforces Round 115 (Rated for Div. 2) B题betset暴力解法

对于 n 个长度为 5 的 01字符串， 你需要把这n个字符串分成数量相等的两组。并且在每一组中选择一个位置（0~4总共5个位置），使这一组的字符串在该位置全为 1 ，且两组所选位置不同。

测试案例数 ( 1 ≤ t ≤ 1 0 4 ) (1 leq t leq 10^4) (1≤t≤104)
每个测试点的字符串数量 ( 2 ≤ n ≤ 1 0 3 ) (2 leq n leq 10^3) (2≤n≤103)

假如枚举两个位置则 C 5 2 = 10 C^2_5 = 10 C52​=10，极限情况 1 0 8 10^8 108, 常数大可能过不了，于是我们用神奇的std::bitset提高速度

#pragma warning(disable:4996)
#include
#include
int nd[11][2] = { {0 ,0}, {1, 2}, {1, 3}, {1, 4}, {1 ,5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5} };//枚举的位置
std::bitset<1005> bi[7];
void solve() {
	for (int i = 1; i <= 6; i++)bi[i].reset();//清空
	int n = 0; scanf("%d", &n);
	if (n & 1) {
		printf("Non");
		return;
	}
	for (int i = 0; i < n; i++) {
		int w = 0;
		for (int j = 1; j <= 5; j++) {
			scanf("%d", &w);
			if (w == 1)bi[j][i] = 1;
		}
		bi[6][i] = 1;//额外装一个全为1 的bitset ,好做比较
	}
	bool flag = 0;
	for (int i = 1; i <= 10; i++) {
		int l = nd[i][0], r = nd[i][1];
		if ((bi[l] | bi[r]) == bi[6]) {
			if (bi[l].count() >= n / 2 && bi[r].count() >= n / 2) {
				flag = 1;
			}
		}
	}
	if (flag)printf("YESn");
	else printf("NOn");
	return;
}
int main() {
	int t = 0;
	scanf("%d", &t);
	while (t--)solve();
	return 0;
}

实际运行时间超乎想象的快