【BZOJ】1057 [ZJOI2007]棋盘制作（悬线法）

题目

传送门：QWQ

分析

先把题目给出的矩阵变换一下，如果$ a[i][j] $中$ i+j \mod 2 = 1 $那么就对$ a[i][j] $取一下反。

接着就是求原图中最大的0、1子矩阵

详见lrj蓝书，悬线法维护最大0、1子矩阵。

代码

 #include<bits/stdc++.h>

 #define left lft

 #define right rght

 using namespace std;

 const int maxn=;

 int left[maxn][maxn], right[maxn][maxn], up[maxn][maxn] ;

 int mp[maxn][maxn];

 int sqr(int x){return x*x;}

 int main(){

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

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

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

             scanf("%d",&mp[i][j]); if((i+j)%) mp[i][j]^=;

     }

     int ans1=,ans2=;

     for(int i=;i<=m;i++) right[][i]=1e9;

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

         left[i][]=; right[i][m]=m;

         int le=,ri=m+;

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

             if(mp[i][j]){

                 up[i][j]=up[i-][j]+; left[i][j]=max(left[i-][j],le+);

             }

             else{ le=j; }

         }

         for(int j=m;j>=;j--){

             if(mp[i][j]){

                 right[i][j]=min(ri-,right[i-][j]);

                 int linelen=right[i][j]-left[i][j]+ ,rowlen=up[i][j];

                 ans1=max(ans1,sqr(min(linelen,rowlen)));

                 ans2=max(ans2,linelen*rowlen);

             }

             else{

                 ri=j; right[i][j]=m;

             }

         }

     }

     memset(right,,sizeof(right)); memset(left,,sizeof(left)); memset(up,,sizeof(up));

     for(int i=;i<=m;i++) right[][i]=1e9;

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

         left[i][]=; right[i][m]=m;

         int le=,ri=m+;

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

             if(!mp[i][j]){

                 up[i][j]=up[i-][j]+; left[i][j]=max(left[i-][j],le+);

             }

             else{ le=j; }

         }

         for(int j=m;j>=;j--){

             if(!mp[i][j]){

                 right[i][j]=min(ri-,right[i-][j]);

                 int linelen=right[i][j]-left[i][j]+ ,rowlen=up[i][j];

                 ans1=max(ans1,sqr(min(linelen,rowlen)));

                 ans2=max(ans2,linelen*rowlen);

             }

             else{

                 ri=j; right[i][j]=m;

             }

         }

     }

     printf("%d\n%d",ans1,ans2);

     return ;

 }