Description
JYY 最近迷上了拼图游戏。作为一个计算机科学家，JYY 有一套黑白色的拼图，他希望通过合理的拼接，使得拼出的最终图案中，能包含面积最大的全白色子矩形。JYY 一共有 \(S\) 块拼图，并且由 \(1\) 到 \(S\) 编号。编号为 \(i\) 的拼图是一个 \(N\) 行的方格矩形，每个方格都为黑色或者白色。一开始 JYY 将他的这 \(S\) 块拼图按照编号顺序左右相连依次放在桌上拼成了一个 \(N\) 行 \(M\) 列（这里 \(M=\sum\left(W_i\right)(1 \leq i \leq S)\) 的大矩形。之后 JYY 发现，可以通过改变这\(S\) 块拼图的连接次序，使得拼成的 \(N\) 行 \(M\) 列的大矩形中，最大全白子矩形面积变大。现在 JYY 想知道，怎么拼才能得到最大的全白子矩形呢? 请你帮助他计算出最佳的拼接方案。
\(1\le S,N,W\le 10^5,N\times \sum W_i\le 10^5,T\le 3\)。
Solution
记 \(M=\sum W_i\)。
注意到数据范围中 \(N\times M\le 10^5\)，这提示我们可以分两种情况进行。
在讨论之前，先思考一下：如果我们已知矩形的上下边界，如何在 \(\mathcal O(M)\) 的时间里得到答案。
显然，最终答案矩形一定是横跨若干个矩形，然后是左右两端的矩形的一部分（可能没有）。不妨设上下边界分别是 \(l,r\)。那么我们先找出在 \([l,r]\) 全是 \(0\) 的矩形，这些矩形肯定是放中间的。然后再去寻找左右边界。可以记录每个矩形从左或右开始在 \([l,r]\) 中最多有几列，并把其中的最大值所对应的矩形放在左右端点。但是可能某一矩形被同时放在左右端点。为了防止这种情况，需要再统计一个次大值。这个复杂度是 \(\mathcal O(M)\)。
回到上面的讨论。若 \(N\le M\)，那么 \(N\le\sqrt{10^5}\)，我们就可以直接枚举上下边界，用上文的做法即可，总复杂度 \(\mathcal O(N^2M)\)。反之，那我们统计出每个点上方的第一个 \(1\) 的位置，记为 \(up_{i,j}\)，然后以 \([up_{i,j},i]\) 作为左右边界，同样使用上文的做法即可。总复杂度 \(\mathcal O(NM^2)\)。
另外，由于每个矩形的大小不能保证一个较小的范围，所以直接存会爆空间，因此我们要二维转一维存图。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
int T,num,n,m,ans,w[N],st[N],ed[N],a[N],sum[N],up[N];
char ch[N];
int id(int x,int y)
{
if (x<1||y<1) return 0;
return (y-1)*n+x;
}
int getsum(int xx1,int yy1,int xx2,int yy2) {return sum[id(xx2,yy2)]-sum[id(xx1-1,yy2)]-sum[id(xx2,yy1-1)]+sum[id(xx1-1,yy1-1)];}
void calc(int l,int r)
{
if (l>r) return;
for (int i=1,res=0;i<=num;++i)
{
for (int j=st[i];j<=ed[i];++j)
{
if (getsum(l,j,r,j)==0) ++res;
else res=0;
ans=max(ans,res*(r-l+1));
}
}
int lmx[2][2],rmx[2][2],len=0;
memset(lmx,0,sizeof(lmx));
memset(rmx,0,sizeof(rmx));
for (int i=1;i<=num;++i)
{
int llen=0,rlen=0;
for (int j=st[i];j<=ed[i];++j)
if (getsum(l,j,r,j)==0) llen++;
else break;
for (int j=ed[i];j>=st[i];--j)
if (getsum(l,j,r,j)==0) rlen++;
else break;
if (llen==w[i]) len+=w[i];
else
{
if (llen>lmx[0][0]) lmx[1][0]=lmx[0][0],lmx[1][1]=lmx[0][1],lmx[0][0]=llen,lmx[0][1]=i;
else if (llen>lmx[1][0]) lmx[1][0]=llen,lmx[1][1]=i;
if (rlen>rmx[0][0]) rmx[1][0]=rmx[0][0],rmx[1][1]=rmx[0][1],rmx[0][0]=rlen,rmx[0][1]=i;
else if (rlen>rmx[1][0]) rmx[1][0]=rlen,rmx[1][1]=i;
}
}
ans=max(ans,(r-l+1)*len);
for (int i=0;i<2;++i)
for (int j=0;j<2;++j)
if (lmx[i][1]!=rmx[j][1])
ans=max(ans,(r-l+1)*(len+lmx[i][0]+rmx[i][0]));
}
int main()
{
scanf("%d",&T);
while (T--)
{
m=ans=0;
memset(sum,0,sizeof(sum));
scanf("%d%d",&num,&n);
for (int i=1;i<=num;++i)
{
scanf("%d",&w[i]);
st[i]=m+1;
for (int j=1;j<=n;++j)
{
scanf("%s",ch+1);
for (int k=1;k<=w[i];++k)
a[id(j,m+k)]=ch[k]-'0';
}
m+=w[i];
ed[i]=m;
}
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
sum[id(i,j)]=sum[id(i,j-1)]+sum[id(i-1,j)]-sum[id(i-1,j-1)]+a[id(i,j)];
for (int j=1;j<=m;++j)
for (int i=1;i<=n;++i)
{
if (a[id(i,j)]==1) up[id(i,j)]=i;
else up[id(i,j)]=up[id(i-1,j)];
}
if (n<=m)
{
for (int i=1;i<=n;++i)
for (int j=i;j<=n;++j)
calc(i,j);
}
else
{
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
calc(up[id(i,j)]+1,i);
}
printf("%d\n",ans);
}
return 0;
}