CF548B

thomas_zjl · 2021-07-23 20:17:48 · 题解

一个细节很多的模拟。

题目大意。

• 给我们一个 01 矩阵，有 q 次修改，把这个点的数翻转。
• 再输出连续的 1 最多的一行中连续的 1 的个数。

基本思路。

1. 我先求一下输出连续的 1 最多的一行中连续的 1 的个数，把每一行最多连续的 1 的个数保存，因为后面修改时只改变 1 行中的 1 个点，不会改变其他行的数量。

2. 在每一次询问中 ， 只用再算一次改变的那一个行就可以了，在对每一行最多连续的 1 的个数进行比较出最大值。

下面是完成第一步的代码。

//cnt 代表当前连续 1 的个数的序列长度。
//num 代表这一行最大连续 1 的序列的长度。
//flag 代表是否有 1。
//a[i][j] 代表输入的矩阵。
//ans[i] 代表第 i 行最大连续 1 的序列的长度。
int cnt,num;
bool flag;
for(int i=1;i<=n;i++){
    cnt=num=flag=0;//初始化。
    for(int j=1;j<=m;j++){
        if(a[i][j]==1)//如果这里有一个 1 。
            flag=1;//flag为true。
        if(a[i][j]==a[i][j-1]&&a[i][j]==1)//如果 1 是连续的。
            cnt++;//cnt+1。
        else{//如果有一个 0 。
            if(cnt>0)//当 cnt 不为零时进行判断。
                num=max(cnt+1,num);//cnt 要加 1 是因为没有把第一个 1 算进去。
            cnt=0;//重置cnt。
        }
    }
    if(cnt>0)//最后还要判断一下，因为全部是 1 会输出 0 。
        num=max(cnt+1,num);
    if(flag)//如果这里有 1 。
        ans[i]=max(1,num);//那么 ans[i] 一定比 1 大。
    else//如果没有。
        ans[i]=0;//ans[i] 为 0 。
} 

下面是完成第二步的代码。

int x,y;
while(q--){
    cin>>x>>y;//输入。
    if(a[x][y]==1)
        a[x][y]=0;
    else
        a[x][y]=1;
    //这里是来进行数字的翻转。
    cnt=num=flag=0;
    for(int i=1;i<=m;i++){//只有一层循环，来计算这一行连续 1 的序列的长度。
        if(a[x][i]==1)
            flag=1;
        if(a[x][i]==a[x][i-1]&&a[x][i]==1)
            cnt++;
        else{
            if(cnt>0)
                num=max(cnt+1,num);
            cnt=0;
        }
    }
    if(cnt>0)
        num=max(cnt+1,num);
    int sum=0;
    if(flag)
        ans[x]=max(1,num);
    else
        ans[x]=0;
   //上面的几行代码就是来计算这一行连续 1 的序列的最大长度的，与上一个代码没什么区别。
    for(int i=1;i<=n;i++)
        sum=max(sum,ans[i]);//这里是计算最大的连续 1 的序列的最大长度的。
    cout<<sum<<endl;//输出，换行。
}

#include<bits/stdc++.h>
using namespace std;
int a[501][501];
int ans[501];
int main(){
    ios::sync_with_stdio(false);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    int cnt,num;
    bool flag;
    for(int i=1;i<=n;i++){
        cnt=num=flag=0;
        for(int j=1;j<=m;j++){
            if(a[i][j]==1)
                flag=1;
            if(a[i][j]==a[i][j-1]&&a[i][j]==1)
                cnt++;
            else{
                if(cnt>0)
                    num=max(cnt+1,num);
                cnt=0;
            }
        }
        if(cnt>0)
            num=max(cnt+1,num);
        if(flag)
            ans[i]=max(1,num);
        else
            ans[i]=0;
    } 
   //上面是对每一行最多连续的 1 的个数进行计算。 
    int x,y;
    while(q--){
        cin>>x>>y;
        if(a[x][y]==1)
            a[x][y]=0;
        else
            a[x][y]=1;
        cnt=num=flag=0;
        for(int i=1;i<=m;i++){
            if(a[x][i]==1)
                flag=1;
            if(a[x][i]==a[x][i-1]&&a[x][i]==1)
                cnt++;
            else{
                if(cnt>0)
                    num=max(cnt+1,num);
                cnt=0;
            }
        }
        if(cnt>0)
            num=max(cnt+1,num);
        int sum=0;
        if(flag)
            ans[x]=max(1,num);
        else
            ans[x]=0;
        for(int i=1;i<=n;i++)
            sum=max(sum,ans[i]);
        cout<<sum<<endl;
    }
   //上面是对每一个询问并只针对那一行进行计算，在进行输出答案。
}