【ST表维护最值下标】删除字符

逃离我推掉我的手 2024-03-25 09:56 82阅读 0赞

**这道题感觉思路差不多了，但是就差怎么去维护最值下标了**

题意：

![002bdd1bcc1d316b306c6ba50d1358ba.png][]

思路：

首先是一个贪心策略：先选全局最小的，再去选局部最小的，区间一点点缩小

即，先选\[1,n-t\]中的最小值，下标为p1

然后再去\[p1+1,n-t+1\]选最小,下标为p2

再去\[p2+1,n-t+2\]选最小，下标为p3

....

那么我们就用ST表维护最小值下标即可

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e5+10;
    
    vector<int> v;
    string s;
    int n,t;
    int f[mxn][33],lg[mxn];
    int query(int l,int r){
        int k=lg[r-l+1];
        if(s[f[l][k]]<=s[f[r-(1<<k)+1][k]]) return f[l][k];
        return f[r-(1<<k)+1][k];
    }
    void solve(){
        cin>>s>>t;
        n=s.size();
        s=" "+s;
        for(int i=1;i<=n;i++) f[i][0]=i;
        for(int j=1;j<=30;j++){
            for(int i=1;i+(1<<(j-1))<=n;i++){
                if(s[f[i][j-1]]<=s[f[i+(1<<(j-1))][j-1]]) f[i][j]=f[i][j-1];
                else f[i][j]=f[i+((1<<j-1))][j-1];
            }
        }
        int st=0;
        for(int i=1;i<=n-t;i++){
            if(st+1>t+i) continue;
            int tmp=query(st+1,t+i);
            v.push_back(s[tmp]);
            st=tmp;
        }
        for(int i=0;i<v.size();i++) cout<<(char)v[i];
    }
    void init(){
        lg[1]=0;
        for(int i=2;i<mxn;i++) lg[i]=lg[i>>1]+1;
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[002bdd1bcc1d316b306c6ba50d1358ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6fe0725678d7470cb648696e126d5654.png

发表评论取消回复

表情：

评论列表（有 0 条评论，82人围观）

还没有评论，来说两句吧...

相关阅读

相关 ST表

ST表什么是ST表 ST表是一种神奇的数据结构，它虽说有它的短板——不支持修改，但它的特点同样很鲜明——短小精悍，能做到 $ O (n \\log n) ...

谁践踏了优雅/ 2024年04月20日 10:34/ 0 赞/ 56 阅读

相关【ST表维护最值下标】删除字符

这道题感觉思路差不多了，但是就差怎么去维护最值下标了题意： ![002bdd1bcc1d316b306c6ba50d1358ba.png][] 思路：首先是一个贪心

逃离我推掉我的手/ 2024年03月25日 09:56/ 0 赞/ 83 阅读

相关【模版】Sparse-Table｜ST表｜基于ST表的RMQ

文章目录 Sparse Table（ST表）详细介绍模版(最小值版本) -------------------- Sparse Table（S

﹏ヽ暗。殇╰゛Y/ 2022年12月28日 12:46/ 0 赞/ 148 阅读

相关 654 最大二叉树（递归、ST表）

1. 问题描述：给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的最大二叉树定义如下：二叉树的根是数组 nums 中的最大元素。左子树

川长思鸟来/ 2022年08月29日 09:51/ 0 赞/ 139 阅读

相关 ST表

转载博主:[点这里][Link 1] ST表学习作用：ST算法是用来求解给定区间RMQ的最值，本文以最小值为例举例：给出一数组A\[0~5\] = \{5,4

￡神魔★判官ぃ/ 2022年05月28日 07:25/ 0 赞/ 204 阅读

相关 st 表算法模板

借鉴于：[https://blog.csdn.net/Hanks\_o/article/details/77547380][https_blog.csdn.net_Hanks_

左手的ㄟ右手/ 2022年05月15日 12:23/ 0 赞/ 199 阅读

相关基础数据维护-删除

基础数据维护-删除开发工具与关键技术：VS、基础数据维护-删除作者：黄桂康撰写时间： 2019年04月28日删除-可指定哪条数据删除，也可多

た入场券/ 2022年04月24日 19:06/ 0 赞/ 155 阅读

相关删除数字求最小值

删除数字求最小值: \include<iostream> \include<malloc.h> \include<stdlib.h> \include<stri

水深无声/ 2022年04月22日 11:38/ 0 赞/ 216 阅读

相关浅谈ST表

咱们先来前情引导一下　　假如你的面前有一个区间【1，6，2，8，7，4，6，3，9，3，0】请问，这个区间的最大值是森魔？最小值是森魔？（千万别说你不知道）答案显然：m

雨点打透心脏的1/2处/ 2021年11月05日 12:24/ 0 赞/ 267 阅读

相关 ST表模板

普通存最大值，最小值 int a[maxn]; ll Max[MAXN][21]; ll Query(int l,int r) {

梦里梦外;/ 2021年09月19日 05:40/ 0 赞/ 249 阅读