【AtCoder Regular Contest 081 F】Flip and Rectangles | Mrsrz's blog

结论题，单调栈。

题目大意：

给定 $H\times W$ 的棋盘，每个位置为黑色或白色。

你可以任意执行以下操作：

• 选择一行或一列，将这上面的所有格子的颜色翻转。

问进行操作后，棋盘上的最大全黑子矩形的面积最大是多少。

题解：

这题有一个结论：对于任意 $2\times 2$ 的子矩形，它能被染成全黑，当且仅当其中恰好有偶数个格子为白色。

我们发现，在这个结论下，共用格子是不会产生冲突的。也就是说所有 $2\times 2$ 的子矩形都可以独立考虑。

那么我们将可能染黑的 $2\times 2$ 的格子找出来（记录左上角），然后找它的面积最大的子矩形即可。

这个可以用单调栈在 $O(H\times W)$ 里求出。

这样求出的答案的两条边长度至少为 $2$，所以还有一条边长度为 $1$ 的情况。此时最大方案为 $\max(H,W)$。答案取 $\max$ 即可。

Code：

#include<cstdio>
#include<algorithm>
using std::max;
const int N=2333;
int pre[N][N],L[N],R[N];
int n,m,h,t,top;
char mp[N][N];
int sta[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%s",mp[i]+1);
    for(int i=1;i<n;++i){
        for(int j=1;j<m;++j){
            int x=(mp[i][j]=='.')+(mp[i][j+1]=='.')+(mp[i+1][j]=='.')+(mp[i+1][j+1]=='.');
            if(x%2==0)pre[j][i]=pre[j-1][i]+1;else pre[j][i]=0;
        }
    }
    int ans=n;
    if(ans<m)ans=m;
    for(int j=1;j<m;++j){
        int*P=pre[j];
        sta[top=1]=L[1]=1;
        *sta=0;
        for(int i=2;i<n;++i){
            while(top&&P[i]<=P[sta[top]])--top;
            L[i]=sta[top]+1;
            sta[++top]=i;
        }
        sta[top=1]=R[n-1]=n-1;
        *sta=n;
        for(int i=n-2;i;--i){
            while(top&&P[i]<=P[sta[top]])--top;
            R[i]=sta[top]-1;
            sta[++top]=i;
        }
        for(int i=1;i<n;++i)ans=max(ans,(R[i]-L[i]+2)*(P[i]+1));
    }
    printf("%d\n",ans);
    return 0;
}