自动搬运

查看原文

来自洛谷，原作者为

	Cxny Take me to where you are, won't you?

搬运于2025-08-24 22:20:54，当前版本为作者最后更新于2022-07-30 15:05:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

显然，如果没有必须将两块较小块染成一黑一白的限制，我们一定可以染出目标矩阵。

因此，对于当前较大的一个块，我们可以先将四小块分别染色，再考虑如何染整块的 $0$ 和 $1$ 使得代价最小。

一种贪心是，将染成 $0$ 和 $1$ 的额外代价从小到大排序，将额外代价最小的染色。

但很明显，这种做法是错误的。对于如下矩阵：

$$\begin{matrix} 0,0,0,0\\ 0,0,0,1\\ 0,0,0,0\\ 0,1,0,0 \end{matrix}$$

左上方子矩阵正常染色最小代价为 $1$ ，染成 $1$ 的额外代价为 $4$ ；而右上方子矩阵正常染色最小代价为 $0$ ，染成 $1$ 额外代价为 $3$ 。二者之差相等。

程序可能会将左上方子矩阵染成 $1$ 而将右上方子矩阵染成 $0$ ，算得最小代价为 $6$ 。

然而，最优解得到的矩阵可以是：

$$\begin{matrix} 0,0,1,1\\ 0,0,1,1\\ 0,0,0,0\\ 0,1,0,1 \end{matrix}$$

最小代价为 $4$ 。

在考虑染整块时直接枚举将哪块染成 $0$ 或 $1$ 即可。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 513;
int n, a[maxn][maxn], ans[maxn][maxn], res[5][13], cnt1[5][13];
pair<int, int> tot[5];
int chosen[5], bst[5];
char s[maxn][maxn];
int count(int x, int y, int sz){
	int ret = 0;
	for(int i = 1; i <= sz; i++) for(int j = 1; j <= sz; j++)
		ret += a[x + i - 1][y + j - 1];
	return ret;
}
pair<int, int> getxy(int x, int y, int sz, int type){
	if(type == 2) x += sz;
	else if(type == 3) y += sz;
	else if(type == 4) x += sz, y += sz;
	return {x, y};
}
void color(int x, int y, int sz, int type, int col){
	auto tmp = getxy(x, y, sz, type);
	x = tmp.first, y = tmp.second;
	for(int i = 1; i <= sz; i++) for(int j = 1; j <= sz; j++)
		ans[x + i - 1][y + j - 1] = col;
}
int solve(int x, int y, int sz, int dep){
	if(sz == 1) return ans[x][y] = a[x][y], 0;//大小为 1 的矩阵可任意染色
	int mid = sz >> 1, ret = 0;
	
	//正常染子矩阵
	res[1][dep] = solve(x, y, mid, dep + 1), res[2][dep] = solve(x + mid, y, mid, dep + 1);
	res[3][dep] = solve(x, y + mid, mid, dep + 1), res[4][dep] = solve(x + mid, y + mid, mid, dep + 1);
	ret = sz * sz;
	auto tmp = getxy(x, y, mid, 1);
	cnt1[1][dep] = count(tmp.first, tmp.second, mid);
	tmp = getxy(x, y, mid, 2);
	cnt1[2][dep] = count(tmp.first, tmp.second, mid);
	tmp = getxy(x, y, mid, 3);
	cnt1[3][dep] = count(tmp.first, tmp.second, mid);
	tmp = getxy(x, y, mid, 4);
	cnt1[4][dep] = count(tmp.first, tmp.second, mid);
	for(int i = 1; i <= 4; i++) chosen[i] = i;
	
	//枚举
	do{
		int cur = mid * mid - cnt1[chosen[1]][dep] + cnt1[chosen[2]][dep] + res[chosen[3]][dep] + res[chosen[4]][dep];
		if(cur < ret){
			ret = cur;
			for(int i = 1; i <= 4; i++) bst[i] = chosen[i];
		}
	}while(next_permutation(chosen + 1, chosen + 5));
	
	color(x, y, mid, bst[1], 1);//染色
	color(x, y, mid, bst[2], 0);
	return ret;
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%s", s[i] + 1);
		for(int j = 1; j <= n; j++) a[i][j] = s[i][j] - '0';
	}
	printf("%d\n", solve(1, 1, n, 0));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++) printf("%d", ans[i][j]);
		puts("");
	}
	return 0;
}