B4229 棋盘题解

1. 题意解释

给出一个

n\times n

的黑白交替网格，每次对某一行或某一列做黑白翻转操作，求每次操作后的黑白格四连通块个数。

2. 思路

我们不难发现一开始的黑白网格可以看做是对全黑（或全白）图做奇数（或偶数）行列翻转得到。

我们考虑记录每行及每列的操作数。

考虑如何从行列中的操作数求出连通块个数。

不难发现每个连通块一定是呈方格状，且每个连通块一定对应一行上的连通块和一列上的连通块，所以我们只需要求出一行及一列的黑白连通块数，相乘即得到总的连通块数量。

对于一行（或一列）的连通块数，不难发现我们可以在每次操作时比较这一行（或这一列）操作的那个格子与其两边的格子颜色，然后就可以很简单的计算了。

3. 代码实现

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,op,a,row[100100],col[100100],rowcnt,colcnt;
signed main(){
    cin>>n;
    for(int i=2;i<=n;i+=2){
    	row[i]=col[i]=1;
	}
	cin>>q;
	rowcnt=colcnt=n;
	while(q--){
		cin>>op>>a;
		if(op==1){
			if(a==1){
				if(row[a]==row[a+1]){
					rowcnt=min(rowcnt+1,n);
				}
				else{
					rowcnt=max(rowcnt-1,1ll);
				}
				row[a]^=1;
			}
			else if(a==n){
				if(row[a]==row[a-1]){
					rowcnt=min(rowcnt+1,n);
				}
				else{
					rowcnt=max(rowcnt-1,1ll);
				}
				row[a]^=1;
			}
			else{
				if(row[a]==row[a+1]&&row[a]==row[a-1]){
					rowcnt=min(rowcnt+2,n);
				}
				else if(row[a]!=row[a+1]&&row[a]!=row[a-1]){
					rowcnt=max(rowcnt-2,1ll);
				}
				row[a]^=1;
			}
		}
		if(op==2){
			if(a==1){
				if(col[a]==col[a+1]){
					colcnt=min(colcnt+1,n);
				}
				else{
					colcnt=max(colcnt-1,1ll);
				}
				col[a]^=1;
			}
			else if(a==n){
				if(col[a]==col[a-1]){
					colcnt=min(colcnt+1,n);
				}
				else{
					colcnt=max(colcnt-1,1ll);
				}
				col[a]^=1;
			}
			else{
				if(col[a]==col[a+1]&&col[a]==col[a-1]){
					colcnt=min(colcnt+2,n);
				}
				else if(col[a]!=col[a+1]&&col[a]!=col[a-1]){
					colcnt=max(colcnt-2,1ll);
				}
				col[a]^=1;
			}
		}
		cout<<rowcnt*colcnt<<'\n';
	}
    return 0;
}

文章操作

1. 题意解释

2. 思路

3. 代码实现

相关推荐

评论

B4229 棋盘题解