[ARC135D] Add to Square

[ARC135D] Add to Square

考虑最后只要求绝对值即可，我们将网格黑白染色，取反所有的黑格。

显然，一次操作是将白格 \(+x\)，黑格 \(-x\)。

容易发现，这样的一次操作不会改变每行和每列的和。

我们声称这个条件是充要的，也就是说任意两个行列和相同的网格都可以互相转化。

考虑证明，发现前 \(n-1\) 行和前 \(m-1\) 列可以随意变动，剩下的部分必然能够一样。

我们最后的目标是最小化，考虑构造一个理论的下界。

记第 \(i\) 行的和为 \(p_i\)，第 \(i\) 列的和为 \(q_i\)，则答案为：

\[\max(\sum\limits_{i=1}^{n} |p_i|,\sum\limits_{i=1}^{m} |q_i|) \]

不妨假设 \(\sum\limits_{i=1}^{n} |p_i| \geq \sum\limits_{i=1}^{m} |q_i|\)。

要取到这个值，每一行的正负性与和都会被确定。

接下来考虑构造证明，我们不断进行以下操作：

• 找到符号相同的 \(p_i\) 和 \(q_j\)，将 \(a_{i,j}\) 加上绝对值较小的一个

同时此时 \(p_i\) 和 \(q_j\) 也要相应变化。

接下来 \(p\) 的和与 \(q\) 的和相同，又无同号，即 \(p\) 和 \(q\) 必有全 \(0\)。

假设 \(p\) 不全为 \(0\)，进行以下操作：

• 找到符号不同的 \(p_i\) 和 \(p_j\)，分别选择一列加减绝对值的较小值

这个操作不会改变列的和，我们最后可以完成操作。

假设 \(q\) 不全为 \(0\)，进行以下操作：

• 找到符号不同的 \(q_i\) 和 \(q_j\)，分别选择一行加减绝对值的较小值

这个操作不会改变行的和，我们最后可以完成操作。

然而这样还会有正负号的问题，我们不能被上面的假设局限。

也就是说，我们按照过程求出的答案，必然是正确的。

时间复杂度 \(O(nm)\)。

//Ad astra per aspera
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
long long a[510][510],x[510],y[510];
long long my_abs(long long num){
	if(num>=0) return num;
	else return -num;
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);
			if((i+j)&1){
				a[i][j]=-a[i][j];
			}
			x[i]+=a[i][j];
			y[j]+=a[i][j];
			a[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(x[i]>0  &&  y[j]>0){
				long long num=min(my_abs(x[i]),my_abs(y[j]));
				a[i][j]+=num;
				x[i]-=num;
				y[j]-=num;
			}
			if(x[i]<0  &&  y[j]<0){
				long long num=min(my_abs(x[i]),my_abs(y[j]));
				a[i][j]-=num;
				x[i]+=num;
				y[j]+=num;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(x[i]>0  &&  x[j]<0){
				long long num=min(my_abs(x[i]),my_abs(x[j]));
				a[i][1]+=num;
				a[j][1]-=num;
				x[i]-=num;
				x[j]+=num;
			}
			if(x[i]<0  &&  x[j]>0){
				long long num=min(my_abs(x[i]),my_abs(x[j]));
				a[i][1]-=num;
				a[j][1]+=num;
				x[i]+=num;
				x[j]-=num;
			}
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=i+1;j<=m;j++){
			if(y[i]>0  &&  y[j]<0){
				long long num=min(my_abs(y[i]),my_abs(y[j]));
				a[1][i]+=num;
				a[1][j]-=num;
				y[i]-=num;
				y[j]+=num;
			}
			if(y[i]<0  &&  y[j]>0){
				long long num=min(my_abs(y[i]),my_abs(y[j]));
				a[1][i]-=num;
				a[1][j]+=num;
				y[i]+=num;
				y[j]-=num;
			}
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if((i+j)&1){
				a[i][j]=-a[i][j];
			}
			ans+=my_abs(a[i][j]);
		}
	}
	printf("%lld\n",ans);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%lld ",a[i][j]);
		}
		printf("\n");
	}
	return 0;
}