对于 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<stdio.h> #include<bitset> 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("No\n"); 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("YES\n"); else printf("NO\n"); return; } int main() { int t = 0; scanf("%d", &t); while (t--)solve(); return 0; }
实际运行时间超乎想象的快