专栏文章

题解：B4229 [常州市赛 2024] 棋盘

ffeifeize
B4229题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minj8dto
此快照首次捕获于
2025/12/02 03:18
3 个月前
此快照最后确认于
2025/12/02 03:18
3 个月前
查看原文
对于这一题，首先对于每一行每一列维护联通，在线编写每次修改当前行状态数，然后相乘就行了。
怎么维护呢？

1：修改的是边界的

分类讨论：若与最近的一样，当前的联通数 +1+1，否则 −1-1。

2：修改中间

照样分类：若只与左右其中一个一样，当前的联通数不变；若都一样，则当前的联通数 +2+2；若都不一样，则当前的联通数 −2-2。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+7;

int n,q,a,b,hh,ll, h[N],l[N];

signed main()
{
    cin>>n>>q;
    
    for(int i=1;i<=n;i++)h[i]=l[i]=(i%2==1)?0:1;
    h[0]=h[n+1]=l[0]=l[n+1]=2;
    hh=n,ll=n;
    while(q--)
    {
        cin>>a>>b;
        if(a==1) 
        {
            
            if(b==1||b==n)
            {
                if(h[b-1]!=h[b]&&h[b+1]!=h[b])hh-=1;
                else hh+=1;
            }
            else if(h[b-1]==h[b]&&h[b+1]==h[b])hh+=2;
            else if(h[b-1]!=h[b]&&h[b+1]!=h[b])hh-=2;
            h[b]=(h[b]+1)%2; 
        }
        else 
        {
            if(b==1||b==n)
            {
                if(l[b-1]!=l[b]&&l[b+1]!=l[b])ll-=1;
                else ll+=1;
            }
            else if(l[b-1]==l[b]&&l[b+1]==l[b])ll+=2;
            else if(l[b-1]!=l[b]&&l[b+1]!=l[b])ll-=2;
            l[b]=(l[b]+1)%2;
        }
        cout<<ll*hh<<endl; 
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...