好久没做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][20],k,n; char a[maxn]; void RMQ(){ for(int i=1;i<=n;i++)dp[i][0]=i; for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++) if( a[dp[i][j-1]] <= a[dp[i+(1<<(j-1))][j-1]] ) dp[i][j]=dp[i][j-1]; else dp[i][j]=dp[i+(1<<(j-1))][j-1]; } int query(int l,int r){ int k=log(r-l+1.0)/log(2.0); if(a[dp[l][k]] <= a[dp[r-(1<<k)+1][k]]) return dp[l][k]; return dp[r-(1<<k)+1][k]; } int main(){ cin>>k>>a+1; n=strlen(a+1); int m=n-k+1; RMQ(); int t=1; 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=0;i<v.size();i++) cout<<v[i]; }