CF1864D 题解

我们注意到对如图倒三角形上的所有点操作都会影响到目标点。

那么我们可以维护两个前缀和，第一个前缀和表示如下的点是否操作

第二个前缀和表示这些点是否操作

这样我们求出了前缀和之后，将两个前缀和异或一下就知道该点是否要操作了。

#include<bits/stdc++.h>
using namespace std;
int t,n,b[2][3005],c[2][3005],ans;
char a[3005][3005];
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		ans=0;
		for(int i=1;i<=n;i++)cin>>(a[i]+1);
		for(int j=0;j<=n+1;j++)b[0][j]=b[1][j]=c[0][j]=c[1][j]=0;
		for(int i=1;i<=n;i++){
			int sum=0;
			for(int j=1;j<=n;j++){
				b[1][j]=b[0][j+1]^sum;
				c[1][j]=c[0][j-1]^sum;
				int nowans=b[1][j]^c[1][j-1];
				if(nowans^(a[i][j]-'0'))ans++,sum^=1,b[1][j]^=1,c[1][j]^=1;
			}
			b[1][n+1]=b[1][n];
			for(int j=1;j<=n+1;j++)b[0][j]=b[1][j],c[0][j]=c[1][j];
		}
		cout<<ans<<"\n";
	}
	return 0;
}