P11521

Inui_Sana · 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();
    }
}