一道非常简单的贪心题

思路如下：

作为每一个象限，只需要把这四个象限的点中 . 的个数和 # 的个数取一个最小值加进答案，而对于修改的点，只需要把答案加上原本的 . 和 # 的个数个数的最小值和修改后的 . 和 # 的个数的最小值的差值输出就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
int q,mp[1005][1005];
int n;
int main() {
	cin>>n>>q;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			char a;
			cin>>a;
			if(a=='.')mp[i][j]=1;
		}
	}
	int ans=0;
	for(int i=1; i<=n/2; i++) {
		for(int j=1; j<=n/2; j++) {
			int gs=0;
			if(mp[i][j]==1)gs++;
			if(mp[i][n-j+1]==1)gs++;
			if(mp[n-i+1][j]==1)gs++;
			if(mp[n-i+1][n-j+1]==1)gs++;
			ans+=min(gs,4-gs);
		}
	}
	cout<<ans<<'\n';
	for(int Q=1; Q<=q; Q++) {
		int a,b;
		cin>>a>>b;
		int i,j;
		if(a>n/2)i=n+1-a;
		else i=a;
		if(b>n/2)j=n+1-b;
		else j=b;
		int ygs=0;
		if(mp[i][j]==1)ygs++;
		if(mp[i][n-j+1]==1)ygs++;
		if(mp[n-i+1][j]==1)ygs++;
		if(mp[n-i+1][n-j+1]==1)ygs++;
		mp[a][b]=(mp[a][b]+1)%2;
		ygs=min(4-ygs,ygs);
		int gs=0;
		if(mp[i][j]==1)gs++;
		if(mp[i][n-j+1]==1)gs++;
		if(mp[n-i+1][j]==1)gs++;
		if(mp[n-i+1][n-j+1]==1)gs++;
		gs=min(gs,4-gs);
		ans+=gs-ygs;
		cout<<ans<<'\n';
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int mp[N][N];
int main() {
	ios::sync_with_stdio(False);cin.tie(0);cout.tie(0);
	int n,q;cin>>n>>q;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			char a;cin>>a;
			mp[i][j]=(a=='.')?1:0;
		}
	}
	int ans=0;
	for(int i=1; i<=n/2; i++) {
		for(int j=1; j<=n/2; j++) {
			int gs=0;
			if(mp[i][j]==1)gs++;
			if(mp[i][n-j+1]==1)gs++;
			if(mp[n-i+1][j]==1)gs++;
			if(mp[n-i+1][n-j+1]==1)gs++;
			ans+=min(gs,4-gs);
		}
	}
	cout<<ans<<'\n';
	for(int Q=1; Q<=q; Q++) {
		int a,b;
		cin>>a>>b;
		int i,j;
		if(a>n/2)i=n+1-a;
		else i=a;
		if(b>n/2)j=n+1-b;
		else j=b;
		int ygs=0;
		if(mp[i][j]==1)ygs++;
		if(mp[i][n-j+1]==1)ygs++;
		if(mp[n-i+1][j]==1)ygs++;
		if(mp[n-i+1][n-j+1]==1)ygs++;
		mp[a][ b ]=1-mp[a][ b ];
		ygs=min(4-ygs,ygs);
		int gs=0;
		if(mp[i][j]==1)gs++;
		if(mp[i][n-j+1]==1)gs++;
		if(mp[n-i+1][j]==1)gs++;
		if(mp[n-i+1][n-j+1]==1)gs++;
		gs=min(gs,4-gs);
		ans+=gs-ygs;
		cout<<ans<<'\n';
	}
	return 0;
}