Hack #1103 - QOJ.ac

2 2
1 2
3 4
1 4
2 3

这组 hack 正确答案是 $1$（没错，讽刺的是，被hack的程序输出的答案才是对的），因为两个矩阵根本就没有大小为 $2$ 的公共子矩阵。

但是 std 却输出 $2$。

错因就是 std 没有考虑边界情况，如果两个数只差一，但是前一个数在右边界，后一个数在左边界，不能判定为相同的子矩阵，但是 std 错误实现（事实上，ICPC 银川站的官方题解确实体现了它会犯这种错误）导致它将这种情况判断为相同子矩阵。

具体而言，错误的实现（没加边界判定，悬线法）如下：Submission #699655 - QOJ.ac

#include<bits/stdc++.h>
#define N 1100
#define up(a,b,c)for(int a=b;a<=c;++a)
#define dn(a,b,c)for(int a=b;a>=c;--a)
using namespace std;
int n,m,a[N][N],p[N*N],u[N],l[N],r[N],rs;
int main()
{
    cin>>n>>m;
    up(i,1,n)up(j,1,m)cin>>a[i][j],p[a[i][j]]=(i-1)*m+j;
    up(i,1,n)
    {
        up(j,1,m)
        {
            cin>>a[i][j],a[i][j]=p[a[i][j]],
            u[j]=i>1&&a[i-1][j]+m==a[i][j]?u[j]+1:1,
            l[j]=r[j]=j;
            while(a[i][l[j]-1]+1==a[i][l[j]]&&u[l[j]-1]>=u[j])l[j]=l[l[j]-1];
        }
        dn(j,m,1)
        {
            while(a[i][r[j]]+1==a[i][r[j]+1]&&u[r[j]+1]>=u[j])r[j]=r[r[j]+1];
            rs=max(rs,u[j]*(r[j]-l[j]+1));
        }
    }
    cout<<rs;
    return 0;
}

正确的实现如下：Submission #699660 - QOJ.ac

#include<bits/stdc++.h>
#define N 1100
#define up(a,b,c)for(int a=b;a<=c;++a)
#define dn(a,b,c)for(int a=b;a>=c;--a)
using namespace std;
int n,m,a[N][N],p[N*N],u[N],l[N],r[N],rs;
int main()
{
    cin>>n>>m;
    up(i,1,n)up(j,1,m)cin>>a[i][j],p[a[i][j]]=(i-1)*m+j;
    up(i,1,n)
    {
        up(j,1,m)
        {
            cin>>a[i][j],a[i][j]=p[a[i][j]],
            u[j]=i>1&&a[i-1][j]+m==a[i][j]?u[j]+1:1,
            l[j]=r[j]=j;
            while(a[i][l[j]-1]%m&&a[i][l[j]-1]+1==a[i][l[j]]&&u[l[j]-1]>=u[j])l[j]=l[l[j]-1];
        }
        dn(j,m,1)
        {
            while(a[i][r[j]]%m&&a[i][r[j]]+1==a[i][r[j]+1]&&u[r[j]+1]>=u[j])r[j]=r[r[j]+1];
            rs=max(rs,u[j]*(r[j]-l[j]+1));
        }
    }
    cout<<rs;
    return 0;
}

@clrs97 和 @nike0good 请出来解释一下情况，如果这确实是出题人的一时疏忽，由于它放过了大量错解，应该尽快补救。