【BZOJ1057】【ZJOI2007】棋盘制作

最大全0子矩阵+最大全0子正方形

没啥区别悬线法

// <1057.cpp> - 07/28/16 08:16:11
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=2010;
const int INF=1e9;
bool a[MAXN][MAXN];
int k[MAXN],l[MAXN],r[MAXN];
int n,m,ans1,ans2;
void get(){
    for(int j=1;j<=m;j++)k[j]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)k[j]=a[i][j]*(k[j]+1);
        for(int j=1;j<=m;j++){
            if(!k[j])continue;
            for(l[j]=j;k[l[j]-1]>=k[j];l[j]=l[l[j]-1]);
        }
        for(int j=m;j;j--){
            if(!k[j])continue;
            for(r[j]=j;k[r[j]+1]>=k[j];r[j]=r[r[j]+1]);
            ans1=max(ans1,min(k[j],r[j]-l[j]+1));
            ans2=max(ans2,k[j]*(r[j]-l[j]+1));
        }
    }
}
int main(){
    n=gi(),m=gi();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)a[i][j]=gi()^(i+j)&1;
    get();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)a[i][j]^=1;
    get();
    printf("%d\n%d",ans1*ans1,ans2);
    return 0;
}

// <1057.cpp> - 07/28/16 08:16:11

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=2010;

const int INF=1e9;

bool a[MAXN][MAXN];

int k[MAXN],l[MAXN],r[MAXN];

int n,m,ans1,ans2;

void get(){

for(int j=1;j<=m;j++)k[j]=0;

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

for(int j=1;j<=m;j++)k[j]=a[i][j]*(k[j]+1);

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

if(!k[j])continue;

for(l[j]=j;k[l[j]-1]>=k[j];l[j]=l[l[j]-1]);

}

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

if(!k[j])continue;

for(r[j]=j;k[r[j]+1]>=k[j];r[j]=r[r[j]+1]);

ans1=max(ans1,min(k[j],r[j]-l[j]+1));

ans2=max(ans2,k[j]*(r[j]-l[j]+1));

}

int main(){

n=gi(),m=gi();

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

for(int j=1;j<=m;j++)a[i][j]=gi()^(i+j)&1;

get();

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

for(int j=1;j<=m;j++)a[i][j]^=1;

get();

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

return 0;

}