[AHOI2014/JSOI2014]拼图

链接：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 #include #include #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