XCPC Notes

Appearance

发布时间：2023-11-22

悬线法 ​

悬线法的适用范围是单调栈的子集。具体来说，悬线法可以应用于满足以下条件的题目：

  • 需要在扫描序列时维护单调的信息；
  • 可以使用单调栈解决；
  • 不需要在单调栈上二分。

引入 ​

SP1805 HISTOGRA - Largest Rectangle in a Histogram ​

11
如图所示，在一条水平线上有 n个宽为 1的矩形，求包含于些矩形的最大子矩形面积（图中的阴影部分的面积即所求答案）。
显然，这是一道经典单调栈题目
单调栈代码如下

cpp
void solve(){
    ll n;
    while(cin>>n&&n!=0){
        stack<ll> st;
        vector<ll> a(n+1);
        for(int i=0;i<n;i++)cin>>a[i];
        a[n]=-1;//保证最后全部数出栈
        ll ans=0;
        for(int i=0;i<=n;i++){
            int x=-1;
            while(!st.empty()&&a[st.top()]>a[i]){
                x=st.top();
                st.pop();
                ans=max(ans,1ll*(i-x)*a[x]);
            }
            if(x!=-1){
                a[x]=a[i];
                st.push(x);//关键将准备要插入的块的长度延长至最后一个删除的块，才能确保答案正确
                continue;
            }
            else st.push(i);
        }
        cout<<ans<<"\n";
    }
}

将每一个高度看作一条悬线，可以左右移动，则该高度对应的长度即为左右可移动的长度
定义 lil_i 为第 ii 个所能到达的左边界

  • li=1l_i=1,说明到达最左端
  • 若ai>ali−1若a_i>a_{l_i-1},则说明不能扩展
  • 否则可以继续扩展,且 li=lli−1l_i=l_{l_i-1}
    右边界r同理
cpp
void solve(){
    ll n;
    while(cin>>n&&n!=0){
        vector<ll> a(n+1),l(n+1),r(n+1);
        iota(l.begin()+1,l.end(),1);
        iota(r.begin()+1,r.end(),1);
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=2;i<=n;i++){
            while(l[i]>1&&a[i]<=a[l[i]-1])l[i]=l[l[i]-1];
        }
        for(int i=n-1;i>=1;i--){
            while(r[i]<n&&a[i]<=a[r[i]+1])r[i]=r[r[i]+1];
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans=max(ans,(r[i]-l[i]+1)*a[i]);
        }
        cout<<ans<<"\n";
    }
}

UVA1619 感觉不错 Feel Good ​

给出正整数 n和一个长度为n的数列a,求 [l,r][l,r],满足：
(∑i=lrai)⋅mini=lrai(\sum_{i=l}^{r}a_i) \cdot min_{i=l}^{r}a_i

求最大值和相应的最小区间的两个端点 思路：枚举 aia_i为最小值，看左边界和右边界，变成和上一题一样，再预处理前缀和即可

cpp
ll a[N],l[N],r[N],sum[N],n;
bool g=1;
void solve(){
    while(cin>>n){
        memset(a,-1,sizeof a);
        if(!g){
            cout<<"\n";
        }
        else g=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
            l[i]=r[i]=i;
        }
        for(int i=1;i<=n;i++){
            while(a[i]<=a[l[i]-1])l[i]=l[l[i]-1];
        }
        for(int i=n;i>=1;i--){
            while(a[i]<=a[r[i]+1])r[i]=r[r[i]+1];
        }
        ll ans=0;
        int ansl=1,ansr=1;
        for(int i=1;i<=n;i++){
            ll tmp=(sum[r[i]]-sum[l[i]-1])*a[i];
            if(ans<tmp){
                ans=tmp;
                ansl=l[i],ansr=r[i];
            }
            else if(ans==tmp&&ansr-ansl>r[i]-l[i])ansr=r[i],ansl=l[i];
        }
        cout<<ans<<"\n"<<ansl<<" "<<ansr<<"\n";
    }
}

最大子矩形 O(NM)O(NM) ​

定义数组
hi,jh_{i,j} 表示第j列以i为底所能到达的最大高度,即碰到障碍物或者上边界，全部初始化为1

li,jl_{i,j} 表示在第i行中j所能到达的最左边界，初始化为j

ri,jr_{i,j}同理

然后从左枚举更新l,从右枚举更新r,具体视题目而定

当 ai,j和ai−1,ja_{i,j} 和a_{i-1,j}满足题目要求能存在于同一矩形时：

  • hi,j=hi−1,j+1h_{i,j}=h_{i-1,j}+1
  • li,j=max(li,j,li−1,j)l_{i,j}=max(l_{i,j},l_{i-1,j})
  • ri,j=min(ri,j,ri−1,j)r_{i,j}=min(r_{i,j},r_{i-1,j})

P4147玉蟾宫 ​

题意：
F表示空地，输出最大空地面积

以下写法仅限于矩形内只有一种元素,如下面的棋盘那道题这种写法就失效了

cpp
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<char>> ch(n+1,vector<char>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>ch[i][j];
    }
    vector<int> a(m+1),l(m+1),r(m+1);
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ch[i][j]=='F')a[j]++;
            else a[j]=0;
            l[j]=r[j]=j;
        }
        for(int j=1;j<=m;j++){
            while(l[j]!=1&&a[j]<=a[l[j]-1])l[j]=l[l[j]-1];
        }
        for(int j=1;j<=m;j++){
            while(r[j]!=m&&a[j]<=a[r[j]+1])r[j]=r[r[j]+1];
        }
        for(int j=1;j<=m;j++){
            ans=max(ans,(ll)(r[j]-l[j]+1)*a[j]);
        }
    }
    cout<<ans*3;
}

模板 ​

cpp
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<char>> a(n+1,vector<char>(m+1));
    vector<vector<int>> h(n+1,vector<int>(m+1)),l(n+1,vector<int>(m+1)),r(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            h[i][j]=1;
            l[i][j]=r[i][j]=j;
        }
        for(int j=2;j<=m;j++){
            if(a[i][j]==a[i][j-1]&&a[i][j]=='F')l[i][j]=l[i][j-1];
        }
        for(int j=m-1;j>=1;j--){
            if(a[i][j]==a[i][j+1]&&a[i][j]=='F')r[i][j]=r[i][j+1];
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>1){
                if(a[i][j]==a[i-1][j]&&a[i][j]=='F'){
                    h[i][j]=h[i-1][j]+1;
                    l[i][j]=max(l[i][j],l[i-1][j]);
                    r[i][j]=min(r[i][j],r[i-1][j]);
                }
            }
            if(a[i][j]=='F')ans=max(ans,(ll)(r[i][j]-l[i][j]+1)*h[i][j]);
        }
    }
    cout<<ans*3;
}

例题 ​

P5943 [POI2002] 最大的园地 ​

题意：
输出由0组成的最大面积

cpp
void solve(){
    int n;
    cin>>n;
    vector<vector<int>> a(n+1,vector<int>(n+1)),h(n+1,vector<int>(n+1)),l(n+1,vector<int>(n+1)),r(n+1,vector<int>(n+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cin>>a[i][j];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            l[i][j]=r[i][j]=j;
            h[i][j]=1;
        }
        for(int j=2;j<=n;j++){
            if(a[i][j]==a[i][j-1]&&a[i][j]==0)l[i][j]=l[i][j-1];
        }
        for(int j=n-1;j>=1;j--){
            if(a[i][j]==a[i][j+1]&&a[i][j]==0)r[i][j]=r[i][j+1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i>1&&a[i][j]==a[i-1][j]&&a[i][j]==0){
                l[i][j]=max(l[i][j],l[i-1][j]);
                r[i][j]=min(r[i][j],r[i-1][j]);
                h[i][j]=h[i-1][j]+1;
            }
            int x=r[i][j]-l[i][j]+1;
            if(a[i][j]==0)ans=max(ans,x*h[i][j]);
        }
    }
    cout<<ans;
}

P1169 [ZJOI2007] 棋盘制作 ​

题意：
矩阵内只有黑和白，输出能分割的黑白相间的最大矩形和正方形
细节：只需将if条件从相等改成不等

cpp
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> a(n+1,vector<int>(m+1)),h(n+1,vector<int>(m+1)),l(n+1,vector<int>(m+1)),r(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    int ans=0,res=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            l[i][j]=r[i][j]=j;
            h[i][j]=1;
        }
        for(int j=2;j<=m;j++){
            if(a[i][j]!=a[i][j-1])l[i][j]=l[i][j-1];
        }
        for(int j=m-1;j>=1;j--){
            if(a[i][j]!=a[i][j+1])r[i][j]=r[i][j+1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>1&&a[i][j]!=a[i-1][j]){
                l[i][j]=max(l[i][j],l[i-1][j]);
                r[i][j]=min(r[i][j],r[i-1][j]);
                h[i][j]=h[i-1][j]+1;
            }
            int x=r[i][j]-l[i][j]+1;
            int y=min(x,h[i][j]);
            ans=max(ans,x*h[i][j]);
            res=max(res,y*y);
        }
    }
    cout<<res<<"\n"<<ans;
}

P2701 [USACO5.3] 巨大的牛棚Big Barn ​

法一：普通dp做法

cpp
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> dp(n+1,vector<int>(n+1,1));
    vector<vector<char>> ch(n+1,vector<char>(n+1,'.'));
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        ch[x][y]='#';
        dp[x][y]=0;
    }
    for(int i=1;i<=n;i++)dp[0][i]=dp[i][0]=0;
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(ch[i][j]=='.'){
                dp[i][j]=max(min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1,dp[i][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans=max(dp[i][j],ans);
        }
    }
    cout<<ans;
}

法二：悬线法

cpp
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1),l(n+1),r(n+1);
    vector<vector<char>> ch(n+1,vector<char>(n+1,'.'));
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        ch[x][y]='#';
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(ch[i][j]=='.')a[j]++;
            else a[j]=0;
            l[j]=r[j]=j;
        }
        for(int j=1;j<=n;j++){
            while(l[j]!=1&&a[j]<=a[l[j]-1])l[j]=l[l[j]-1];
        }
        for(int j=1;j<=n;j++){
            while(r[j]!=n&&a[j]<=a[r[j]+1])r[j]=r[r[j]+1];
        }
        for(int j=1;j<=n;j++){
            ans=max(ans,min(a[j],r[j]-l[j]+1));
        }
    }
    cout<<ans;
}

障碍物法 O(T2)O(T^2) ​

此法适用于障碍物稀疏，而N和M较大时的情况

P1578 奶牛浴场 ​

先看主要算法步骤：
11
11
11
有如下三种情况：

  • 左边界必定为障碍物
  • 右边界必定为障碍物
  • 左右边界为矩形边界
    可以加入四个点表示矩形的四个端点，然后按x从小到大排序，第一二种情况就可以 O(T2)O(T^2) 枚举出来 第三种情况即按y排序，一长度为x的最大值n，另一长度就是两点y的差值
cpp
void solve(){
    int l,w,n;
    cin>>l>>w>>n;
    vector<PLL> a;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        a.emplace_back(x,y);
    }
    n+=4;
    a.emplace_back(0,0);
    a.emplace_back(0,w);
    a.emplace_back(l,0);
    a.emplace_back(l,w);
    sort(a.begin(),a.end(),[&](PLL x,PLL y){
        return x.x<y.x;
    });
    ll ans=0;
    for(int i=0;i<n;i++){
        ll x1=a[i].x,x2=a[i].x,y1=0,y2=w;
        for(int j=i+1;j<n;j++){
            x2=a[j].x;
            ans=max(ans,(x2-x1)*(y2-y1));
            if(a[j].y<a[i].y)y1=max(y1,a[j].y);
            else y2=min(y2,a[j].y);
        }
        x1=a[i].x,x2=a[i].x,y1=0,y2=w;
        for(int j=i-1;j>=0;j--){
            x2=a[j].x;
            ans=max(ans,(x1-x2)*(y2-y1));
            if(a[j].y<a[i].y)y1=max(y1,a[j].y);
            else y2=min(y2,a[j].y);
        }
    }
    sort(a.begin(),a.end(),[&](PLL x,PLL y){
        return x.y<y.y;
    });
    for(int i=0;i<n-1;i++)ans=max(ans,(a[i+1].y-a[i].y)*l);
    cout<<ans;
}

P8404 [CCC2022 J5] Square Pool ​

罗恩想在他的n×n 的正方形院子里建一个正方形游泳池，但他的院子里有T 棵树。你的任务是确定他可以建造的最大的方形游泳池的边长。
思路：
与上一题不同，上一题障碍物可以和边重合，这题不行
因此要换个角度，注意到最大矩形边界要么与给定边界重合要么刚好被树挡住，因此向四个角的外面加4棵树
假定左右边界是被树挡住，那么可以从左到右枚举，与上一题一样维护上下边界，如果上下边界小于左右则直接break，否则更新答案；同理再枚举一遍上下

cpp
void solve(){
    int n;
    cin>>n;
    int t;
    cin>>t;
    vector<PLL> a;
    a.emplace_back(0,0);
    a.emplace_back(0,n+1);
    a.emplace_back(n+1,0);
    a.emplace_back(n+1,n+1);
    for(int i=0;i<t;i++){
        int x,y;
        cin>>x>>y;
        a.emplace_back(x,y);
    }
    t+=4;
    sort(a.begin(),a.end(),[&](PLL x,PLL y){
        return x.x==y.x?x.y<y.y:x.x<y.x;
    });
    ll ans=0;
    for(int i=0;i<t;i++){
        ll y1=1,y2=n;
        for(int j=i+1;j<t;j++){
            if(y2-y1+1<a[j].x-a[i].x-1)break;
            ans=max(ans,a[j].x-a[i].x-1);
            if(a[j].y<=a[i].y)y1=max(y1,a[j].y+1);
            else y2=min(y2,a[j].y-1);
        }
    }
    sort(a.begin(),a.end(),[&](PLL x,PLL y){
        return x.y==y.y?x.x<y.x:x.y<y.y;
    });
    for(int i=0;i<t;i++){
        ll x1=1,x2=n;
        for(int j=i+1;j<t;j++){
            if(x2-x1+1<a[j].y-a[i].y-1)break;
            ans=max(ans,a[j].y-a[i].y-1);
            if(a[j].x<=a[i].x)x1=max(x1,a[j].x+1);
            else x2=min(x2,a[j].x-1);
        }
    }
    cout<<ans;
}

Wenwei Lin · 2022 — 2025