cf1864D. Matrix Cascade（差分）

https://codeforces.com/contest/1864/problem/D

结论很好猜，直接从上到下做就行
我们可以维护差分数组，表示对下面的影响，逐行往下推就行，当然+和-要分开，因为一个是往前推，一个往后推。
时间复杂度\(O(n^2)\)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int inf=1<<30;
const int N=5005;
char s[N];
int a[N][N],ans,n;
int bp[N],bn[N],cp[N],cn[N],t;
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		fo(i,1,n+1) bn[i]=bp[i]=cp[i]=cn[i]=0;
		
		fo(i,1,n) {
			scanf("%s",s+1);
			fo(j,1,n) a[i][j]=s[j]-'0';
		}
		
		ans=0;
		fo(i,1,n) {
			fo(j,1,n) cn[j]=cp[j]=0;
			
			t=0;
			fo(j,1,n) {
				t+=bp[j]+bn[j];
				
				if ((t+a[i][j])&1) {
					ans++;
					cp[max(1,j-1)]++;
					cn[j+2]--;
				}
				
				cp[max(1,j-1)]+=bp[j];
				cn[j+1]+=bn[j];
			}
			
			fo(j,1,n) bp[j]=cp[j], bn[j]=cn[j];
		}
		
		printf("%d\n",ans);
	}

	return 0;
}