好久没做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];
}

最新文章

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

热门文章

  1. 使用Docker部署javaWeb应用
  2. 20165237 学习基础和C语言基础调查
  3. HashMap、Hashtable、ConcurrentHashMap面试总结
  4. 2017-2018-2 20165325 实验三《Java面向对象程序设计》实验报告
  5. Ubuntu 16.04 Matlab2015b安装
  6. windows下安装MySql + navicat(图形化界面)
  7. CentOS 6与7对比【转】
  8. python下载夏目友人帳
  9. CString/string 区别及其转化
  10. 微信小程序-两个input叠加,多次点击字体变粗或闪动