P4147题解

· · 题解

题解区全是悬线法，但是看到 n \leq 1000 的数据范围，我们可以发现，这道题可以二分！Um_nik 听了会很开心的

这个思路是我在某学校打模拟赛时想出来的，下面我们来讲讲这个神奇思路。

我们知道，一个矩形可以用左上角的坐标和右下角的坐标表示，这是因为这两个点可以确定唯一一条直线，也就是矩形的对角线。显然有一个性质：本题中如果表示左上角的 (x_1,y_1) 和表示右下角的 (x_2,y_2) 可以组成一个全是 F 的矩形，那么 (x_2-k_1,y_2-k_2) 也可以和 (x_1,y_1) 组成一个矩形（注意 1 \leq k_1 \leq (x_2-x_1),1 \leq k_2 \leq (y_2-y_1)）。

那么我们怎么判定是否能组成一个全是 F 的矩形呢？直接扫一遍肯定不行，但是可以二维前缀和。记 F 为 1，R 为 0，预处理二维前缀和，然后算一遍这个矩形里的值之和是否等于矩形的面积，就可以 O(1) 查询了，这让我们的时间复杂度直接除以 n \times m！这成为了我们能过这道题的关键。

我们有了上面这些，就能写出代码了，但注意不能写成这样：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005],f[1005][1005],res=0;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char ch;
            cin>>ch;
            if(ch=='F')a[i][j]=1;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int l=1,r=n,ans=0;
            while(l<=r){
                int mid=(l+r)>>1;
                int ll=1,rr=m,ans2=-1;
                while(ll<=rr){
                    int mmid=(ll+rr)>>1;
                    if((f[mid][mmid]-f[i-1][mmid]-f[mid][j-1]+f[i-1][j-1])==(mid-i+1)*(mmid-j+1))ans2=mmid,ll=mmid+1;
                    else rr=mmid-1;
                }
                if(ans2!=-1)ans=(mid-i+1)*(ans2-j+1),l=mid+1;
                else r=mid-1;
            }
            res=max(res,ans);
        }
    cout<<res*3;
}

那么，为什么不能这样写呢？考虑一种情况。

F F F F F F F
F F F F F F F
F F F F F F F
F F R R R R R
F F R R R R R
F F R R R R R
F F R R R R R
F F R R R R R

可以看到，我们上面的代码直接在左上角坐标 (1,1) 的情况下搜到了 x_2=8，但是正解应该是 x_2=3,y_2=7。所以我们不能这样二分。但是，当 x_2 确定时，y_2 一定可以二分，因为是满足单调性的。若 y_2 不满足情况，y_2+k 一定都不满足情况，因为 y_2 以前必然有一个 R。至此，我们已经确定了一个 O(n^3 \log n) 的做法。我们还可以剪枝一下：在当前的 x_2 下，无论如何都没法取得一个满足要求的矩形，那么可以直接 break 掉，原理同上。另外，当取得的矩形面积已经等于 F 的个数了，也就没必要继续算了。

二分一定要注意边界情况，y_2 一定要在 [y_1,m] 的区间内二分，x_2 也一定要在 [x_1,n] 的区间内枚举。

代码非常好写：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005],f[1005][1005],res=0;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char ch;
            cin>>ch;
            if(ch=='F')a[i][j]=1;//F视为1
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];//前缀和预处理
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            for(int k=i;k<=n;k++){
           if((k-i+1)*(m-j+1)<=res)continue;//多剪掉一个情况
                int ll=j,rr=m,ans=-1;
                while(ll<=rr){//二分
                    int mmid=(ll+rr)>>1;
                    if((f[k][mmid]-f[i-1][mmid]-f[k][j-1]+f[i-1][j-1])==(k-i+1)*(mmid-j+1))ans=(k-i+1)*(mmid-j+1),ll=mmid+1;//判断是否满足要求
                    else rr=mmid-1;
                }
           res=max(res,ans);
                if(ans==-1)break;
                if(ans==f[n][m]){
                    cout<<ans*3;
                    return 0;
                }
                //去掉部分冗余计算
            }
        }
    cout<<res*3;
}

最慢的点跑了 288ms，可以通过。