题解 | 正方

· · 个人记录

https://hydro.ac/d/jkfz2022/p/2

题面描述 给定一个 N×N 的网格，给定两条网格上的路径（保证路径和格线重合），求夹在路径中的最大正方形的大小（正方形的边必须与格线平行）。

例如下图（样例1）：

棕色部分是夹在两条路径中的部分，能取出的最大正方形边长为 44。

输入格式 第一行一个正整数 N 表示网格大小。

第二行一个长度为 2N 的只包含 R,D 的字符串，R，表示向右移动一格，D 表示向下移动一格。保证路径从左上出发，到右下结束。

第三行一个长度为 2N 的字符串表示第二条路径。保证第二条路径不存在在第一条路径下方的部分。

输出格式 输出一行一个整数表示答案。

Samples 输入数据 1 10 DDDDRRDDDDRRRDRDRRRR RRDRDRRRDDRRDDDDRDRD 输出数据 1 4 输入数据 2 6 DDDDDDRRRRRR RDRRDDDRRRDD 输出数据 2 3 数据范围与约定 保证 2≤N≤10^6 。

本题共 50 个测试点。

对于测试点 1\sim 51∼5，保证 N\le 10N≤10。

对于测试点 6\sim 156∼15，保证 N\le 100N≤100。

对于测试点 16\sim 3016∼30，保证 N\le 5000N≤5000。

对于测试点 31 \sim 5031∼50，无特殊限制。

分析

这个题目要我们找到最大的正方形。

初步代码

cin>>n;
    for(int i=1; i<=2*n; i++) {
        cin>>c;
        if(c=='R') {
            x++;
            web[x]=y;
        } else {
            y++;
        }
    }
    x=y=0;
    for(int i=1; i<=2*n; i++) {
        cin>>c;
        if(c=='R') {
            x++;
            web[x]=web[x]-y;
            hi[x]=y;
        } else {
            y++;
        }
    }

web[]记录了上下之间的距离 hi[]记录上面到最顶端的距离 初步处理出了这两个数组

进一步分析

int l=0,h=0;
    for(int i=1; i<=n; i++) {
        l++;
        h=web[i-1]-hi[i];

        if(hi[i]!=hi[i-1]&&min(l,answ-hi[i])<ans) {
            l=1;
            h=web[i];
        }
        if(i==1)h=web[i]-hi[i];
        if(min(l,h)>ans){
            ans=min(l,h);
            ansh=hi[i];
            answ=hi[i]+web[i];
            //answ=hi[i]+ans;
        }
        //ans=max(ans,min(l,h));
        cout<<ans<<' '<<l<<' '<<h<<endl;
    }
    //cout<<endl;
    cout<<ans<<endl;

我们可以所以贪心的思想，分为2种选择

于是我们抛弃这种算法！ 最终算法 我们发现，只要从下面的路径的每一个拐角处向右上角数，就可以知道每一个正方形最大是多少。（请务必结合图像！！）于是，算法诞生！！

    for(int i=1; i<n; i++) {
        if(hi[i]+web[i]>hi[i-1]+web[i-1]){
            ans=max(ans,sze(i));
        }
    //  cout<<sze(i)<<endl;
    }
    //cout<<endl;
    cout<<ans<<endl;

在不断寻找拐角时，找到一个，计算此时的正方形大小（从此拐角向右上方）更新ans的值

int sze(int i){
    int res=0;
    int hh=hi[i]+web[i];
    while(++res){
        hh--;
        if(hi[i+res]>=hh||i+res>n)break;
    }
    return res;
}

i传递的是这个拐角在第i竖 本函数返回是是此时的正方形大小。

非常棒！

最终代码呈上！

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char c;
int web[N],x,y,n,hi[N],ans,answ,ansh,tmp;
int sze(int i){
    int res=0;
    int hh=hi[i]+web[i];
    while(++res){
        hh--;
        if(hi[i+res]>=hh||i+res>n)break;
    }
    return res;
}
int main() {
    freopen("square.in","r",stdin); //读入
    freopen("square.out","w",stdout); //读入
    cin>>n;
    for(int i=1; i<=2*n; i++) {
        cin>>c;
        if(c=='R') {
            x++;
            web[x]=y;
        } else {
            y++;
        }
    }
    x=y=0;
    for(int i=1; i<=2*n; i++) {
        cin>>c;
        if(c=='R') {
            x++;
            web[x]=web[x]-y;
            hi[x]=y;
        } else {
            y++;
        }
    }
    for(int i=1; i<n; i++) {
        if(hi[i]+web[i]>hi[i-1]+web[i-1]){
            ans=max(ans,sze(i));
        }
    //  cout<<sze(i)<<endl;
    }
    //cout<<endl;
    cout<<ans<<endl;
    return 0;
}