首页 > 编程语言 >洛谷题单 算法2-2 常见优化技巧

洛谷题单 算法2-2 常见优化技巧

时间：2024-11-13 15:23:36浏览次数：1  
标签：while 技巧 int 洛谷题 ++ stk -- 算法 vector

洛谷题单 算法2-2 常见优化技巧

单调栈

单调栈最经典的应用，就是在一个数列里寻找距离元素最近的比其大/小的元素位置。

模板题，寻找每个元素右边第一个比它大的元素下标。

stack<int> s;
for(int i=n;i>=1;i--){
       while(s.size()&&a[s.top()]<=a[i]) s.pop();
       f[i]=s.size()?s.top():0;
       s.push(i);
  }

洛谷P1950 长方形

题目链接

思路：

我们维护每个位置最多能向上延伸多少格。然后枚举每个点，计算将其当做底边，它向上延伸的最多格作为高度的长方形有多少个。那么我们只需要去计算左边和右边都各自能延伸到什么地方。那么我们就需要去 查找左边第一个小于该高度的位置 和 右边第一个小于该高度的位置 。显然用单调栈即可维护。但是这里要注意，我们维护左边时，应当查找 左边第一个小于等于该高度的位置， 否则我们就会出现重复计算。那么答案就是简单的乘法原理计算即可。

代码：

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    int n,m;
    cin>>n>>m;
    vector<string> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]="?"+a[i];
    } 
    vector<vector<int>> h(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='*') h[i][j]=0;
            else h[i][j]=h[i-1][j]+1;
        }
    }

    auto calc=[&](int i){
        i64 ret=0;
        vector<int> l(m+1),r(m+1);
        stack<int> stk;
        for(int j=1;j<=m;j++){
            while(stk.size()&&h[i][stk.top()]>h[i][j]) stk.pop();
            l[j]=stk.size()?stk.top():0;
            stk.push(j);
        }
        while(stk.size()){
            stk.pop();
        }

        for(int j=m;j;j--){
            while(stk.size()&&h[i][stk.top()]>=h[i][j]) stk.pop();
            r[j]=stk.size()?stk.top():m+1;
            stk.push(j);
        }

        for(int j=1;j<=m;j++){
            ret+=(j-l[j])*(r[j]-j)*h[i][j];
        }
        return ret;
    };

    i64 ans=0;
    for(int i=1;i<=n;i++){
        ans+=calc(i);
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

单调队列

滑动窗口维护区间最值问题

for(int i=0;i<n;i++){
     if(hh<=tt&&k<i-q[hh]+1) hh++;
     while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
     q[++tt]=i;
     if(i+1>=k) printf("%d ",a[q[hh]]);
    }

洛谷P2216 [HAOI2007] 理想的正方形 -- 二维单调队列

题目链接

模板题：

给你一个矩阵，维护所有子矩阵的最值。

思路：

我们先维护每一行长度为 \(n\) 的所有子矩阵的最值 \(xmax\) 和 \(xmin\) 。然后只需要这两个数组再用单调队列维护

列的最值即可。

代码：

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    int a,b,n;
    cin>>a>>b>>n;
    vector<vector<int>> g(a+1,vector<int>(b+1));
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            cin>>g[i][j];
        }
    } 

    vector<vector<int>> xmax(a+1,vector<int>(b+1));
    auto xmin=xmax,maxn=xmax,minn=xmax;

    vector<int> q(1010),qq(1010);
    for(int i=1;i<=a;i++){
        int h=0,t=-1;
        int hh=0,tt=-1;
        for(int j=1;j<=b;j++){
            if(h<=t&&j-q[h]+1>n) h++;
            while(h<=t&&g[i][q[t]]<=g[i][j]) t--;
            q[++t]=j;
            if(j>=n) xmax[i][j-n+1]=g[i][q[h]];
            
            if(hh<=tt&&j-qq[hh]+1>n) hh++;
            while(hh<=tt&&g[i][qq[tt]]>=g[i][j]) tt--;
            qq[++tt]=j;
            if(j>=n) xmin[i][j-n+1]=g[i][qq[hh]];
        }
    }

    for(int i=1;i+n-1<=b;i++){
        int h=0,t=-1;
        int hh=0,tt=-1;
        for(int j=1;j<=a;j++){
            if(h<=t&&j-q[h]+1>n) h++;
            while(h<=t&&xmax[q[t]][i]<=xmax[j][i]) t--;
            q[++t]=j;
            if(j>=n) maxn[j-n+1][i]=xmax[q[h]][i];
            
            if(hh<=tt&&j-qq[hh]+1>n) hh++;
            while(hh<=tt&&xmin[qq[tt]][i]>=xmin[j][i]) tt--;
            qq[++tt]=j;
            if(j>=n) minn[j-n+1][i]=xmin[qq[hh]][i];
        }
    }

    int ans=1e9;
    for(int i=1;i+n-1<=a;i++){
        for(int j=1;j+n-1<=b;j++){
            ans=min(ans,maxn[i][j]-minn[i][j]);
        }
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

二倍经验

只需要维护最大值即可，只不过子矩阵变成了 \(r\times s\) 的。

三倍经验

数组初始化为 \(-1\)，因为 \(t\) 可能为 \(0\) ，表示一开始这块像素就是坏的。

然后如果该子矩阵的最小值不为 \(-1\)，那么用子矩阵最大值更新答案即可。

尺取法/双指针

P1714 切蛋糕 单调队列优化/线段树

题目链接

相当于在 最大子段和 问题上增加了一个长度限制。

考虑 \(f_i\) 为以 \(i\) 结尾的最长子段和。

\(f_i=max(S_i-S_j)\) ,其中 \(j \in [i-m,i-1]\)。

\(S_i\) 是定值，因此可以拿出来。

\(f_i=S_i-min(S_j)\) , 其中 \(j \in [i-m,i-1]\)。

所以我们直接求区间最小值即可。离线操作，所以线段树，ST表都可以解决。

但是代码相对不好写。发现区间长度固定，滑动窗口 模型，直接单调队列即可。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    int n,m;
    cin>>n>>m;
    vector<i64> a(n+1),s(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }

    vector<int> q(2*n+1);
    int hh=0,tt=-1;
    i64 ans=a[1],minn=0;

    for(int i=1;i<=n;i++){
        ans=max(ans,s[i]-minn);
        if(hh<=tt&&i-q[hh]+1>m) hh++;
        while(hh<=tt&&s[q[tt]]>=s[i]) tt--;
        q[++tt]=i;
        if(i>=m) minn=s[q[hh]];
        else minn=min(minn,s[i]);  
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

最大子矩形问题

洛谷P1578 奶牛浴场

题目链接

现将四个顶点加入障碍物中，然后按照横坐标排序，从左往右和从右往左扫描更新答案。

最后再按纵坐标排序，相邻两项之间构成一个矩形。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

//最大子矩形问题
void Showball(){
    int l,w,n;
    cin>>l>>w>>n;
    vector<array<int,2>> a(n+4);
    for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1];
    //设置4个顶点为障碍点
    a[n++]={0,0};a[n++]={0,w};a[n++]={l,0};a[n++]={l,w};
    
    int L,R,U,D;
    //从左往右搜
    sort(a.begin(),a.end(),[&](array<int,2> x,array<int,2> y){
        return x[0]==y[0]?x[1]<y[1]:x[0]<y[0];
    });

    int ans=0;
    for(int i=0;i<n;i++){
        L=a[i][0],D=0,U=w;
        for(int j=i+1;j<n;j++){
            R=a[j][0];
            ans=max(ans,(R-L)*(U-D));
            if(a[j][1]<a[i][1]) D=max(D,a[j][1]);
            else U=min(U,a[j][1]); 
        }
    }

    //从左往右搜

    for(int i=n-1;i>=0;i--){
        L=a[i][0],D=0,U=w;
        for(int j=i-1;j>=0;j--){
            R=a[j][0];
            ans=max(ans,(L-R)*(U-D));
            if(a[j][1]<a[i][1]) D=max(D,a[j][1]);
            else U=min(U,a[j][1]); 
        }
    }

    //处理特殊情况
    sort(a.begin(),a.end(),[&](array<int,2> x,array<int,2> y){
        return x[1]==y[1]?x[0]<y[0]:x[1]<y[1];
    });

    for(int i=0;i<n-1;i++){
        ans=max(ans,l*(a[i+1][1]-a[i][1]));
    }

    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

标签：while,技巧,int,洛谷题,++,stk,--,算法,vector
From： https://www.cnblogs.com/showball/p/18544004

相关文章

  • 非煤矿山算法智慧矿山一体机提升机危险区域违规闯入识别边坡监测预警系统详述
    在矿山行业中，安全始终是最为关键的议题。随着智能化技术的发展，智慧矿山一体机应运而生，它专为矿山安全监控和管理设计，集成了多种智能化功能，以提升矿山的安全监管能力和生产效率。这款设备不仅能够满足矿山场景下的视频智能化建设需求，还能够通过边缘计算技术实现对矿山安全风险的实......
  • 【算法学习】单调队列优化dp
    前言这已经是很基础很模板化的优化了，我们可以理解为用贪心的思路去掉了永远不可能用到的状态，通常用于长度固定是个区间、最大值且满足单调性的题目。如果一个选手比你小，还比你强，你就永远也打不过他了。这很残酷但这也是单调队列的思想，虽然现实情况比较多变。P3572[POI2014]PT......
  • 街面环卫算法视频分析服务器沿街晾晒智慧城管算法详解
    在城市精细化管理的背景下，智慧城管和街面秩序维护的需求日益增长。为了提高城市管理效率，确保城市秩序和市容市貌，一款集高清视频监控、智能分析与告警、数据资源共享服务于一体的智能化一体机设备应运而生。本文将详细介绍街面环卫算法视频分析服务器的功能特点以及其在智慧城管和......
  • 视频智能分析网关视频分析网关工服检测算法：提升安全监管效率的关键技术
    随着AI技术的持续发展，智能视频分析网关已经成为多个行业安全监控的关键设备。在这些网关中，工服检测算法作为一项关键技术，利用深度学习和计算机视觉技术，能够实时监控并分析监控视频中工作人员的工服穿着情况。本文将详细分析视频智能分析网关视频分析网关的工服检测算法，并探讨其在......
  • 烟火检测视频分析网关算法网关智慧工厂安全生产视频监管方案
    在数字化时代，企业转型升级已成为实现可持续发展的必由之路。特别是在工业领域，工厂的智能化转型不仅能够提高生产效率，还能加强安全管理，确保员工的健康与安全。TSINGSEE青犀AI智能分析网关V4与安防监控视频管理系统EasyCVR视频融合平台的结合，为工厂提供了一个实现智能化转型、构建智......
  • 百万数据做支撑，智能算法赋能标准查重工作全面升级
    标准查重—快速检查标准重复度—在标准编制过程中，查重工作是确保标准质量、维护其科学性与原创性的重要环节。例如，在编制某一特定行业的产品质量标准时，需要与该行业已有的国家、行业、地方标准进行全面比对，查看是否存在重复条款、相似表述等情况。尤其是在全球化背景下，很多......
  • 高手技巧：如何在 Android 上绕过人脸识别
    人脸识别是Android引入的一项重要安全功能，可帮助用户保护其设备免遭未经授权的访问。如果您想保证文件安全，它非常有用。通常，面部识别的工作原理是使用您的面部作为生物识别标识符来验证某些操作。但是，有时会由于各种原因而失败。可能是相机坏了，或者设备有问题。发生这种情况......
  • 代码随想录算法训练营第二十四天| leetcode93.复原IP地址、 leetcode78.子集、leetcod
    1leetcode93.复原IP地址题目链接：93.复原IP地址-力扣（LeetCode）文章链接：代码随想录视频链接：回溯算法如何分割字符串并判断是合法IP？|LeetCode：93.复原IP地址_哔哩哔哩_bilibili思路：就是将这个字符串符合要求的进行一个收集，然后使用列表存储，最后使用join函数将这个列表进行连......
  • 高级算法LLM大语言模型算法特训 带你转型AI大语言模型算法工程师
    高级算法LLM大语言模型算法特训：转型AI大语言模型算法工程师的指南随着人工智能技术的飞速发展，大语言模型（LargeLanguageModel,LLM）作为自然语言处理（NLP）领域的重要组成部分，正逐步成为各行各业的关键技术支撑。本文将深入探讨高级算法LLM大语言模型算法特训的内容、过程及如何通过......
  • Sql优化技巧总结（面试必刷！！！）
    摘要    近段时间，面试官关于Sql优化的提问已经越来越多了，Sql优化可以说是已经成为了面试必备技能之一。本文从Sql语句、硬件设备以及Java程序三个方面详细的讲解关于Sql优化的技巧。目录摘要一、Sql语句优化1、避免使用Select*总结2、使用（创建）索引2.1、不能......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99