C. Qualification Rounds（思维，特情）

C. Qualification Rounds

题意
给定 n * m 的 01 矩阵。
问，是否可以从中挑选出若干行，满足：

• 对于每一列来说，挑选出的所有行中，1 的个数最多是总行数的一半。

$1\le n\le 10^5,1\le k\le 4$

思路
也就是说，每一列 0 的个数要大于等于 1 的个数。

考虑特殊情况，最多只需要看两行。

如果发现存在一行全是 0，肯定满足。
如果发现存在两行，每一列至少有一个 0，那么也是满足的。

也就是找，是否存在两行，其对应位置相与之后，所有位置都为 0。也就是，将每一行转为二进制之后，是否存在两行相与为0。

n 最大为 10^5，但是 k 最大为 4，所以最多有 2^4 种行，二进制枚举 0到2^4，看哪些二进制出现过，二重循环暴力出现过的二进制看是否相与为 0。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], f[N];

signed main(){
	Ios;
	cin >> n >> m;
	
	int flag = 0;
	
	for(int i=1;i<=n;i++)
	{
		int x = 0;
		for(int j=0;j<m;j++)
		{
			int t; cin >> t;
			if(t) x += 1<<j;
		}
		f[x] = 1;
		if(x == 0) flag = 1; //仅有一个都为0的行都满足，提前标记 
	}
	
	for(int i=0;i<1<<m;i++)
	{
		if(!f[i]) continue;
		for(int j=i+1;j<1<<m;j++)
		{
			if(!f[j]) continue;
			if((i & j) == 0) flag = 1; //注意 & 比 == 的优先级低，要加括号！！ 
		}
	}
	if(flag) cout << "YES\n";
	else cout << "NO\n";
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

经验
一开始做的时候倒是想只拿两行的情况，但是也没手推一下，觉得不行就没再想。。
其实该画画的，如果画不出来别的情况那这样就是满足的，或者能直接证明最好。

所以有了思路一定要再想想，不要直接否定，也不要盲目肯定，先画画几个样例再说！说不定就是对的！！

还有就是要注意运算符优先级，注意 & 的优先级比 == 低，判断 i&j 是否为 0 是要加括号！
还有注意 i & (1<> j & 1 的结果才是 0 或 1。
(i >> j & 1) == 0 这里也要加括号！