牛客周赛 66 F 小苯的字符提前

原题链接:F-小苯的字符提前

题意：给出长度为n的字符串，定义move(i)串为将第i个字母移到首位的字符串，对于move(1)到move(n)的字符串，求出字典序第k小的move串。

思路：思维题。第一步，可以将move串分成26类，每一类为不同的小写字符开头，这样就可以确定字典序第k小的move串以什么字符开头。第二步，观察这些move串的特点，可以发现开头字母确定的情况下，这些串的字典序和第i个字符之后第一个不同的字符的大小有关。

如果第一个不同的字符比第i个字符小，那么i之后的move串的字典序都会大于当前串。例如：aababc，move(3)=baaabc，move(5)=baabac，可以发现b>a，如果移动3之后的b，会让3位置的b掉到4位置，move(3)和move(5)相比四位置的a<b,所以3位置之后全部的b都会在4位置上小于a，那么就可以确定move(3)的字典序小于后面全部的。

如果第一个不同的字符比第i个字符大，那么i之后的move串的字典序都会小于当前串。例如：aabcba，move(3)=baacba，move(5)=baabca，可以发现c>b，如果移动3之后的b，会让3位置的b掉到4位置，move(3)和move(5)相比4位置的c>b,所以3位置之后全部的b都会在4位置上小于c，那么就可以确定move(3)的字典序大于后面全部的。

对于这些move串的相对字典序，可以使用deque来倒序维护。

//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
random_device rd;
mt19937_64 mt(rd());
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007,P=131;
void Jiuyuan()
{string s;map<char,ll> op;ll n,k;cin>>n>>k;cin>>s;s=' '+s+' ';for(int i=1;i<=n;i++){op[s[i]]++;}ll nm=0;for(auto v:op)//确定串的首位字符是什么 {if(nm+v.second>=k){k-=nm;nm=v.first;break;}nm+=v.second;}deque<ll> kp;vector<ll> last(n+10);//确定i位置后第一个不同的位置在什么地方 ll id=n+1;for(int i=n;i>=1;i--){if(i<n&&s[i]==s[i+1]){last[i]=last[i+1];}else last[i]=i+1;}for(int i=n;i>=1;i--){if(s[i]!=nm)continue;//如果不是要提到首位的字符直接跳过 ll x=last[i];if(s[i]<s[x])//因为是倒序维护，把这个位置插入deque的最后一位，这个move串的字典序比之前出现的都大 {kp.push_back(i);}else if(s[i]>s[x])kp.push_front(i);//因为是倒序维护，把这个位置插入deque的第一位，这个move串的字典序比之前出现的都小 }for(int i=1;i<k;i++)kp.pop_front();cout<<s[kp.front()];for(int i=1;i<=n;i++){if(i==kp.front())continue;cout<<s[i];}cout<<endl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;cin>>T;while(T--){Jiuyuan();}return 0;
}