CF1864D Matrix Cascade 题解

首先把式子拆一下，可以知道 \(x-i \ge |y-j|\) 等价于 \(x-y \ge i-j\) 和 \(x+y \ge i+j\)，注意到每次操作 \((i,j)\)，影响到的点 \((x,y)\) 均要满足 \(x>i\)，那么我们每次就必须要按照从上往下的顺序进行，否则上面的点无法影响到，即从第一行开始操作。

又注意到对于 \((i,j)\) 如果执行了两次操作相当于没有执行操作，因此对于 \((i,j)\) 我们最多执行一次操作。

所以得出了一种贪心求法：从第一行往下，每次碰到不是 \(0\) 的就修改，可以证明一定步数最小。时间复杂度 \(O(n^4)\) 无法承受。

我们考虑优化修改的过程，注意到我们修改的时候区域是连续的，类似一个三角形的形状，所以我们可以类比二维前缀和与二维差分，维护两条直线来进行优化，分别是斜率为 \(1\) 和斜率为 \(-1\) 的两条直线。

我们用 \(b\) 数组维护斜率为 \(-1\) 的直线，用 \(c\) 数组维护斜率为 \(1\) 的直线，注意到状态只有 \(\{1,0\}\)，因此我们可以用异或来简便操作。

时间复杂度 \(O(n^2)\)。

#include <cstdio>

int t;
int n;
int a[3005][3005];
int b[3005][3005],c[3005][3005];

void solve() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) scanf("%1d",&a[i][j]);
	}
	int sum=0,tot=0;//sum表示修改次数，tot辅助于修改 
	for(int i=1;i<=n;i++) {//从第一行开始，自上而下 
		for(int j=1;j<=n;j++) {//求出每个格子的状态，要注意边界 
			a[i][j]^=(sum&1);//前面行的操作对当前行的影响，如果有影响到当前可以改变，如果没有影响到在后面与b，c异或时可以抵消 
			if(j-2>=1) a[i][j]^=b[i-1][j-2];
			if(j+2<=n) a[i][j]^=c[i-1][j+2];
		}
		for(int j=1;j<=n;j++) {//统计有多少个格子在第i行被执行操作 
			if(a[i][j]) ++sum;
		}
		tot=0;
		for(int j=1;j<=n;j++) {//下传 
			tot^=a[i][j];
			b[i][j]=b[i-1][j-1]^tot;
		}
		tot=0;
		for(int j=n;j>=1;j--) {//下传，注意边界 
			tot^=a[i][j];
			if(j!=n) c[i][j]=c[i-1][j+1]^tot;
			else c[i][j]=tot;
		}
	}
	printf("%d\n",sum);
}

int main() {
	scanf("%d",&t);
	while(t--) solve();
	return 0;
}