hiho1460 rmq模板题

时间：2022-05-03 16:24:01

好久没做rmq的题了，今天写了一遍，感觉打表有点像区间dp

/*

给定长为n的字符串，要求在字符串中选择k个字符，

选择的子系列字典序最小

因为选择k个字符，那么就是去掉n-k个字符

那么[1,n-k+1]位中必定选择一个字符

设这个字符在t1位

然后[t1,n-k+2]位中必定选择一个字符

设这个字符在t2位

以此类推

那么问题就是求区间最小字符的下标

rmq即可

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 100005

int dp[maxn][],k,n;

char a[maxn];

void RMQ(){

    for(int i=;i<=n;i++)dp[i][]=i;

    for(int j=;(<<j)<=n;j++)

        for(int i=;i+(<<j)-<=n;i++)

            if( a[dp[i][j-]] <= a[dp[i+(<<(j-))][j-]] )

                dp[i][j]=dp[i][j-];

            else dp[i][j]=dp[i+(<<(j-))][j-];

}

int query(int l,int r){

    int k=log(r-l+1.0)/log(2.0);

    if(a[dp[l][k]] <= a[dp[r-(<<k)+][k]])

        return dp[l][k];

    return dp[r-(<<k)+][k];

}

int main(){

    cin>>k>>a+;

    n=strlen(a+);

    int m=n-k+;

    RMQ();

    int t=;

    vector<char>v;

    v.clear();

    for(int i=m;i<=n;i++){

        t=query(t,i);

        v.push_back(a[t]);

        t++;

    }

    for(int i=;i<v.size();i++)

        cout<<v[i];

}

相关文章