自动搬运

查看原文

来自洛谷，原作者为

	Bronya18C 人活着就是为了和美少女贴贴

搬运于2025-08-24 22:28:42，当前版本为作者最后更新于2022-09-17 11:52:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于本题原唯一题解是错误的贪心，现提供一种有正确性证明的方法。

给一个 $n \times n$ 的 $01$ 矩阵，每次使一行或一列状态反转，问能否用若干次操作后使得最终矩阵的 $1$ 的个数 $\le k$。

本题关键条件为 $k \le n$，不运用此条件我们的贪心无从下手。

这里我们分成两类情况：

• $k<n$

  因为我们最多使用 $k$ 次操作 3 将原矩阵 $1$ 变为 $0$，所以经过操作 1 或 2 后的矩阵 $1$ 的个数 $g$ 满足 $g \le k \lt n$ 。

  运用鸽巢原理可知 $n$ 行里至少有一行全为 $0$。

  我们枚举全为 $0$ 的行，然后我们发现对于当前情况，每一列的操作情况是固定的。

  由于操作为一整行或列反转，因此每一列或行操作次数要么是 $0$ 要么是 $1$，否则可以等价于 $0$ 或 $1$。

  现在我们固定了一行 $i$，规定它最终一定要是 $0$，则对于每一列 $j$，$a_{i,j}=0$ 则这一列不操作，否则 $a_{i,j}=1$ 一定要操作。

  然后我们对其他行进行列的操作（其实相当于异或上 $a_i$ ），然后每一行最后可以进行贪心是否反转，因为列已经固定，且此行的操作不会对其他行有影响。

  即对于每个枚举的行 $i$ 统计 $ans_i=\sum\limits_{j\not=i} {\min \{\sum_{l=1}^{n}{a_{i,l} \oplus a_{j,l}} , n-\sum_{l=1}^{n}{a_{i,l} \oplus a_{j,l}}\}}$（其中 $\oplus$ 表示异或）。

  最后看是否存在一行 $i$，满足 $ans_i \le k$。

  暴力枚举 $i,j,l$ 是 $\mathcal O(n^3)$ 的。

  用 bitset 优化可做到 $\mathcal O(\dfrac{n^3}{w})$ 。

• $k=n$

  同理，我们首先判断是否能够存在至少有一行全为 $0$ 的解，同 $k<n$ 的情况。

  但 $k=n$ 可能会存在最终每一行恰好都有一个 $1$ 的解。

  我们枚举第一行的哪一位是 $1$，然后先将其异或上 $1$（相当于提前用一次操作 3），此时最终第一行就是全为 $0$ 了。

  此时用了一次操作 3，相当于 $k=n-1$，将第 1 行行当作 $k<n$ 情况中的全为 $0$ 的那行 $i$ 进行求解即可。

  枚举第一行的某一位复杂度为 $\mathcal O(n)$，再枚举剩下的每行每位复杂度为 $\mathcal O(n^2)$，再用 bitset 优化同样可以做到 $\mathcal O(\dfrac{n^3}{w})$。

总时间复杂度 $\mathcal O(\dfrac{n^3}{w})$。

int n,k;
bitset<1005>st[1005];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		char s[1005];
		scanf("%s",s+1);
		for(int j=1;j<=n;j++)
			if(s[j]=='o')st[i][j]=1;
	}
	if(k==n){
		for(int i=1;i<=n;i++){
			st[1].flip(i);
			bool chk=false;
			for(int j=2;j<=n;j++){
				st[j]=st[1]^st[j];
				if(min(st[j].count(),n-st[j].count())>1){
					chk=true;st[j]=st[1]^st[j];
					break;
				}
				st[j]=st[1]^st[j];
			}
			if(!chk){
				puts("DA");
				return 0;
			}
			st[1].flip(i);
		}
	}
	for(int i=1;i<=n;i++){
		int sum=0;
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			st[j]=st[j]^st[i];
			sum+=min(st[j].count(),n-st[j].count());
			st[j]=st[j]^st[i];
		}
		if(sum<=k){
			puts("DA");
			return 0;
		}
	}
	puts("NE");
	return 0;
}