自动搬运

查看原文

来自洛谷，原作者为

	Inui_Sana ばか！へんたい！うるさい！⠀

搬运于2025-08-24 23:08:03，当前版本为作者最后更新于2025-01-12 11:57:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不算难吧，为啥场上没多少人做（

先翻译一下题意：

定义对 01 矩阵的一个操作 $(x_1,y_1,x_2,y_2,k)$ 为，向 $x\in[x_1,x_2],y\in[y_1,y_2]$ 的子矩阵内任意填 01，然后将原子矩阵的元素向左平移 $k$ 个单位，覆盖在矩阵上。

给你两个 01 矩阵 $A,B$。你要对于每一个 $k\in [1,m]$，求出有多少个子矩形，使得对 $A$ 进行操作 $(x_1,y_1,x_2,y_2,k)$ 后，矩阵等于 $B$。

分析一下这个操作，矩形会变成三个不同的部分：在平移后的子矩阵中的，在原子矩阵但是不在平移后的子矩阵中的，完全没有影响的。

• 第一部分，要求平移后对应位置相同。
• 第二部分，没有任何限制。
• 第三部分，要求原本 $A$ 和 $B$ 这些位置就相同。

于是对于一个操作合法，也就是两个限制：

• 平移后子矩形对应位置相同。
• 影响到的位置包含了所有 $A,B$ 不同的位置。

不难发现第二个限制就是对 $x_1,y_1,x_2,y_2$ 有一些限制。于是考虑第一个限制。

考虑枚举 $k$，处理出 $c_{i,j}=[a_{i,j}=b_{i,j-k}]$。那么第一个限制就变成了 $c_{i,j}$ 中，这个位置的矩形全为 $1$。即问题变成了求最大全 $1$ 子矩阵大小。

这是一个经典问题。考虑枚举 $y_1$，对于全部 $x_1$ 求出 $f_{x_1}$ 表示第 $x_1$ 行中，以 $(x_1,y_1)$ 为左端点的最长全 $1$ 段长度。然后对 $f$ 单调栈求出 $l_i,r_i$ 表示左边第一个 $f_j<f_i$ 的 $j$ 和右边第一个 $f_j\le f_i$ 的 $j$。那么答案就是 $\max(r_i-l_i-1)\times f_i$。

但是一个问题是这里有 $x,y$ 的限制。会不会有影响？但是容易发现，在满足对应位置相等的条件下，这个子矩阵的大小更大，在 $x,y$ 的限制中是不劣的，因为影响到的元素变多了。所以只用每次更新答案的时候判断 $(i,l_i+1),(f_i,r_i-1)$ 这个矩阵是否满足条件即可。

还有一点细节：如果移动前后的矩形不交，在一些不太精细的实现中（比如我的），要特判两个矩阵中间几列有不同元素的情况。

时间复杂度 $O(n^3)$。

code：

int n,m,top,a[N][N],b[N][N],c[N][N],f[N],g[N],h[N],st[N];
int pd[N];
char s[N];
void Yorushika(){
	read(n,m);
	rep(i,1,n){
		scanf("%s",s+1);
		rep(j,1,m){
			a[i][j]=s[j]-'0';
		}
	}
	int x1=inf,x2=-inf,y1=inf,y2=-inf;
	rep(i,1,n){
		scanf("%s",s+1);
		rep(j,1,m){
			b[i][j]=s[j]-'0';
			if(a[i][j]!=b[i][j]){
				x1=min(x1,i),y1=min(y1,j);
				x2=max(x2,i),y2=max(y2,j);
				pd[j]=1;
			}
		}
	}
	rep(i,1,m){
		pd[i]+=pd[i-1];
	}
	rep(k,1,m-1){
		mems(c,0);
		rep(i,1,n){
			rep(j,k+1,m){
				c[i][j]=a[i][j]==b[i][j-k];
			}
		}
		mems(f,0),f[0]=f[n+1]=-inf;
		int ans=-1;
		drep(j,m,k+1){
			rep(i,1,n){
				if(c[i][j]){
					f[i]++;
				}else{
					f[i]=0;
				}
			}
			st[top=1]=0;
			rep(i,1,n){
				while(top&&f[st[top]]>=f[i]){
					top--;
				}
				g[i]=st[top]+1;
				st[++top]=i;
			}
			st[top=1]=n+1;
			drep(i,n,1){
				while(top&&f[st[top]]>=f[i]){
					top--;
				}
				h[i]=st[top]-1;
				st[++top]=i;
			}
			rep(i,1,n){
				if(g[i]<=x1&&h[i]>=x2&&j-k<=y1&&j+f[i]>y2&&f[i]&&pd[j-1]-pd[j+f[i]-1-k]<=0){
					ans=max(ans,(h[i]-g[i]+1)*f[i]);
				}
			}
		}
		printf("%d ",ans?ans:-1);
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}