[Agc081F/At2699] Flip and Rectangles

[Agc081F/At2699]

给出一个拥有 \(H\times W\) 个格子的棋盘，每个格子的颜色为黑色或白色。 Snuke 可以进行任意次下列操作：

选择棋盘中的一行或一列，将这一行或一列的颜色翻转（黑变成白，白变成黑） Snuke 想知道，在他进行操作后，棋盘中最大的全黑矩形最大能为多少。

考虑 \(2\times 2\) 方格，当且仅当偶数个黑时，可以做成全黑

大矩形能做成全黑，当且仅当所有 \(2\times 2\) 子格都是偶数个黑

然后就是一个很朴素的单调栈求最大矩形了

注意到答案最小为\(max(n,m)\)，所以最后要处理一下

我大概是菜的连单调栈维护矩形都不会写了

#include <bits/stdc++.h>

using namespace std;

int h[2005],a[2005][2005],b[2005][2005],f[2005],p[2005],r,n,m,ans;

char c[2005][2005];

int main() {

    scanf("%d%d",&n,&m);

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

        scanf("%s",c[i]+1);

        for(int j=1;j<=m;j++) {

            b[i][j] = c[i][j]=='#'?1:0;

        }

    }

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

        for(int j=1;j<m;j++) {

            if((b[i][j]+b[i+1][j]+b[i][j+1]+b[i+1][j+1])%2==0) {

                a[i][j]=1;

            }

        }

    }

    for(int i=1;i<m;i++) h[i]=0;

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

        for(int j=1;j<m;j++) {

            if(a[i][j]) h[j]++;

            else h[j]=0;

        }

        memset(f,0,sizeof f);

        memset(p,0,sizeof p);

        r=0;

        for(int j=1;j<=m;j++) {

            while(r && f[r] >= h[j]) {

                ans=max(ans, (j-p[r-1])*(f[r]+1));

                --r;

            }

            f[++r] = h[j];

            p[r] = j;

            //ans=max(ans, (j-p[1]+2)*(f[1]+1));

        }

        //while(r) if(i-h[p[r]]+1) ans=max(ans, (m-p[r]+1)*(f[r]+1)), r--;

        //if(r) cout<<(m-p[1]+1)<<" "<<(f[1]+1)<<endl;

    }

    cout<<max(ans,max(n,m))<<endl;

}

巴特西

[Agc081F/At2699] Flip and Rectangles - 单调栈,结论

最新文章

热门文章