B4229 棋盘 题解

· · 题解

1. 题意解释

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

2. 思路

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

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

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

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

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

3. 代码实现

#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;
}