思路:悬线法(or)单调栈
提交：2次
错因：正方形面积取错了(QwQ)
题解：
悬线法
讲解：王知昆(dalao)的(PPT)
详见代码：
#include<cstdio>
#include<iostream>
#define ull unsigned long long
#define ll long long
#define R register int
using namespace std;
#define pause (for(R i=1;i<=10000000000;++i))
#define In freopen("NOIPAK++.in","r",stdin)
#define Out freopen("out.out","w",stdout)
namespace Fread {
static char B[1<<15],*S=B,*D=B;
#ifndef JACK
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
#endif
inline int g() {
R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}
inline void gs(char* s) {
register char ch; while(isempty(ch=getchar()));
do *s++=ch; while(!isempty(ch=getchar()));
}
} using Fread::g; using Fread::gs;
namespace Luitaryi {
const int N=4010;
int n,m,a[N][N],l[N][N],r[N][N],h[N][N],S1,S2;
inline void main() {
n=g(),m=g();
for(R i=1;i<=n;++i) for(R j=1;j<=m;++j) a[i][j]=g(),l[i][j]=r[i][j]=j,h[i][j]=1;//刚开始令悬线长度为1，左右边界都是本身。
for(R i=1;i<=n;++i) for(R j=2;j<=m;++j) if(a[i][j]!=a[i][j-1]) l[i][j]=l[i][j-1];//在悬线长度为1时，尝试扩大左右边界
for(R i=1;i<=n;++i) for(R j=m-1; j;--j) if(a[i][j]!=a[i][j+1]) r[i][j]=r[i][j+1];
for(R i=1;i<=n;++i) for(R j=1;j<=m;++j) {
if(i>1) if(a[i][j]!=a[i-1][j]) {//若颜色不相等，尝试合并悬线。
l[i][j]=max(l[i][j],l[i-1][j]),//左端点往大取
r[i][j]=min(r[i][j],r[i-1][j]),//右端点往小取
h[i][j]=h[i-1][j]+1;//悬线长度+1
} R a=r[i][j]-l[i][j]+1,b=min(a,h[i][j]);
S1=max(S1,b*b),S2=max(S2,a*h[i][j]);//计算面积
} printf("%d
%d
",S1,S2);
}
}
signed main() {
Luitaryi::main(); return 0;
}
单调栈
其实单调栈我没有写，但是教练给的标签是单调栈。。。然后稍微想了想又看了看题解(QwQ)
以下引用自@luogu.org lzoi_lhy
从第一行到第n行扫一遍，维护h数组表示从当前格子往上能延伸到的黑白相间的线段（有一条边长为1的矩形）的最长长度
我们可将当前行分为若干条线段，满足每条线段是最长的黑白相间的线段（不能再向左右延伸）
对于每条线段，结合h数组，我们不难发现我们得到了一排高矮不一的长条状的矩形
是不是很熟悉？用单调栈扫一遍即可
如果遇到颜色与上一个相同的格子，就把整个栈弹出来
注意正方形可以在数矩形的时候顺便数出来
#include<cstdio>
#include<iostream>
#include<cstring>
#define X (h[stack[top]])//矩形的宽
#define Y (cur-stack[top-1]-1)//矩形的长
#define Z (min(X,Y))//正方形的边长
using namespace std;
int n,m,top,cur,ans1,ans2,stack[2010],map[2010][2010],h[2010];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j) scanf("%d",&map[i][j]);
for (int j=1;j<=n;++j){
for (int i=1;i<=m;++i)
if (j>1&&map[j][i]!=map[j-1][i]) ++h[i];
else h[i]=1;
cur=1;
while (cur<=m){
stack[0]=cur-1;stack[top=1]=cur++;
while (cur<=m&&(map[j][cur]!=map[j][cur-1])){
while (top&&h[stack[top]]>h[cur])
ans1=max(ans1,Z*Z),ans2=max(ans2,X*Y),--top;
stack[++top]=cur++;
}
while (top) ans1=max(ans1,Z*Z),ans2=max(ans2,X*Y),--top;
}
}
printf("%d
%d
",ans1,ans2);
return 0;
}
2019.07.22