hiho1460 rmq模板题
2024-10-15 09:19:14
好久没做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];
}
最新文章
- mysql大表myisam的导入
- salesforce 零基础学习(二十一)workflow Q&;A
- NOI 2015 荷马史诗【BZOJ 4198】k叉Huffman树
- Python3 连接Mysql
- IE下Checkbox标签的onchange事件兼容
- Uva 11538 - Chess Queen
- jellyfish K-mer analysis and genome size estimate
- JavaScript == VS ===
- linux ant 解决 错误: 找不到或无法加载主类 org.apache.tools.ant.launch.Launcher
- 自定义窗口 mfc
- iOS语音识别,语音播报,文字变语音播报,语音变文字
- bzoj 1193
- XAMPP命令之LAMPP
- 「七天自制PHP框架」第四天:模型关联
- thinkphp分页带数据
- Sublime Text3 快捷键汇总及设置快捷键配置环境变量
- 关于redis分布式锁的实现方式(转载)
- vfd with stm8
- 2018-2019-2 20175328 《Java程序设计》第八周学习总结
- vuex的module的简单实用方法