二维差分前缀和——cf1202D(好题）

直接枚举每个点作为左上角是可以做的，但是写起来较麻烦

有一种较为简单的做法是对一列或一行统计贡献

比如某一行的B存在的区间是L,R那么就有三种情况

　　1.没有这样的区间，即一行都是W，此时这行对答案的贡献一直是1

　　2.R-L+1<=k,那么这一段必须要找一个点代表的矩形来覆盖，可以求出这样的点的存在区间是一个矩形，当且仅当点在这个矩形范围内时，这一行会有1的贡献、

　　3.R-L+1>k,永远不会有贡献

对于情况2，我们用二维的差分来统计一下，最后枚举每个点，看我们选择这个点代表的矩形时，贡献是否达到最大就行

#include<bits/stdc++.h>

using namespace std;

#define N 2005

char mp[N][N];

int n,k,tot,l[N],r[N],u[N],d[N],cnt[N][N];

int main(){

    cin>>n>>k;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            scanf("\n%c",&mp[i][j]);

    memset(l,0x3f,sizeof l);

    memset(u,0x3f,sizeof u);

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++)

            if(mp[i][j]=='B')

                l[i]=min(l[i],j),r[i]=max(r[i],j);

        if(l[i]==0x3f3f3f3f)

            tot++;

        else if(r[i]-l[i]+<=k){

            int x1=max(,i-k+),y1=max(,r[i]-k+);

            int x2=i,y2=l[i];

            cnt[x1][y1]++;cnt[x1][y2+]--;

            cnt[x2+][y1]--;cnt[x2+][y2+]++;

        }

    }

    for(int j=;j<=n;j++){

        for(int i=;i<=n;i++)

            if(mp[i][j]=='B')

                u[j]=min(u[j],i),d[j]=max(d[j],i);

        if(u[j]==0x3f3f3f3f)

            tot++;

        else if(d[j]-u[j]+<=k){

            int x1=max(,d[j]-k+),y1=max(,j-k+);

            int x2=u[j],y2=j;

            cnt[x1][y1]++;cnt[x1][y2+]--;

            cnt[x2+][y1]--;cnt[x2+][y2+]++;

        }

    }

    int ans=;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++){

            cnt[i][j]+=cnt[i-][j]+cnt[i][j-]-cnt[i-][j-];

            ans=max(ans,cnt[i][j]);

        }

    cout<<ans+tot<<endl;

}

巴特西

二维差分前缀和——cf1202D(好题）

最新文章

热门文章