链接：https://www.luogu.com.cn/problem/P4039
题目描述:有一些长为\(n\)，宽为\(w_{i}\)的黑白色矩形，要将它们拼成一个\(n\times m\)的大矩形，求大矩形中最大的全白子矩形的面积的最大值。
题解：话说我一开始只会\(O(n^2m)\)，不会\(O(m^2n)\)，尽管知道这题可以根号分治都不会做。
\(n\times m<=10^5\)，这让人莫名想起CmdOI2019简单的数论题。依照那题的方法，我们可以考虑根号分治，考虑\(O(n^2m)\)与\(O(m^2n)\)两种情况。
\(O(n^2m)\):可以暴力枚举行的左右端点，对于这\(S\)个矩形，我们可将完整的白块放在中间，两边各放两个靠右边\(0\)列最多的块与靠左边\(0\)列最多的块，这样拼是最优的。
\(O(nm^2)\):记每一个点\((i,j)\)离他最近的\(1\)的行为\(up_{i,j}\)，将枚举行的左右端点时换作枚举每个点，判时判左端点为\(up_{i,j}+1\)，右端点为\(i\)的情况即可。
当然，这题有个小坑：每个矩形本身的最大的全白子矩形也要统计到达答案里。
#include<iostream>
#include<cstdio>
#include<vector>
#define inf 1e9
using namespace std;
int n,m,S,w[300001],lst[300001];
int p[300001],up[300001],sum[300001],T[300001],length;
long long ans;
char t;
int f(int l,int r)
{
if (l==0||r==0)
return 0;
return (l-1)*m+r;
}
int getsum(int l,int r,int l2,int r2)
{
return sum[f(r,r2)]-sum[f(l-1,r2)]-sum[f(r,l2-1)]+sum[f(l-1,l2-1)];
}
void solve(int l,int r)
{
long long res=0,ll,rr,maxr=0,maxn=0,maxr2=0,maxn2=0,mixn=0,mixn2=0;
for (int i=1;i<=S;++i)
{
if (getsum(l,r,lst[i-1]+1,lst[i])==0)
res+=w[i];
else
{
for (int j=lst[i-1]+1;j<=lst[i];++j)
if (getsum(l,r,lst[i-1]+1,j)!=0)
{
if (j-lst[i-1]-1>maxn)
{
maxn=j-lst[i-1]-1;
maxr=i;
}
else if (j-lst[i-1]-1>mixn)
mixn=j-lst[i-1]-1;
break;
}
for (int j=lst[i];j>=lst[i-1]+1;--j)
if (getsum(l,r,j,lst[i])!=0)
{
if (lst[i]-j>maxn2)
{
maxn2=lst[i]-j;
maxr2=i;
}
else if (lst[i]-j>mixn2)
mixn2=lst[i]-j;
break;
}
ll=lst[i-1]+1;
rr=-inf;
for (int j=lst[i-1]+1;j<=lst[i];++j)
{
if (getsum(l,r,j,j)==0)
rr=j;
else
{
ans=max(ans,(r-l+1)*(rr-ll+1));
ll=j+1;
}
}
}
}
if (maxr==maxr2)
ans=max(ans,(res+max(mixn2+maxn,mixn+maxn2))*(r-l+1));
else
ans=max(ans,(res+maxn+maxn2)*(r-l+1));
return;
}
void work()
{
ans=length=m=0;
scanf("%d%d",&S,&n);
for (int i=1;i<=S;++i)
{
scanf("%lld",&w[i]);
m+=w[i];
lst[i]=lst[i-1]+w[i];
for (int k=1;k<=n*w[i];++k)
{
++length;
T[length]=0;
while (T[length]!='0'&&T[length]!='1')
T[length]=getchar();
}
}
length=0;
for (int i=1;i<=S;++i)
for (int k=1;k<=n;++k)
for (int j=lst[i-1]+1;j<=lst[i];++j)
{
++length;
p[f(k,j)]=T[length]-'0';
}
int pointer;
for (int i=1;i<=m;++i)
{
pointer=0;
for (int j=1;j<=n;++j)
{
if (p[f(j,i)]==1)
pointer=j;
up[f(j,i)]=pointer;
}
}
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
sum[f(i,j)]=p[f(i,j)]+sum[f(i-1,j)]+sum[f(i,j-1)]-sum[f(i-1,j-1)];
if (n<m)
{
for (int i=1;i<=n;++i)
for (int j=i;j<=n;++j)
solve(i,j);
}
else
{
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (up[f(i,j)]+1<=i)
solve(up[f(i,j)]+1,i);
}
printf("%lld\n",ans);
return;
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
work();
return 0;
}