题面

\(S_n\) 由 \(S_{n-1}\) 去掉一个字母得到，\(S=S_1+S_2+...+S_n\) 给定 \(S_1\) 求 \(S\) 的第 \(N\) 位

solution

我们先考虑怎样去字母能保持字典序最小

显然，我们发现如果一个字母比前面那个字母小，那么我们就要删除前面那个字母

也就是我们要删除一些字母，保持剩余的字母单调递增

如果剩下的字母已经保持单调增了，就从后往前删

另外，我们可以很简单的求出 \(N\) 的位置在第几个 \(S_n\) 的第几位

那么需要删除的数字就是 \(n-1\) 个

至于单调序列如何实现，使用栈就好了

注意这个题要开 \(LL\)

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+5;
int T,Num;
char s[maxn];
char st[maxn];
int top,id[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
signed main(){
    // freopen("C.in","r",stdin);
    // freopen("C.out","w",stdout);
    T=read();
    while(T--){
        scanf("%s",s+1);
        int pos=read(),len=strlen(s+1);
        int Long=0;
        for(int i=1;i<=len;i++){
            Long+=len-i+1;
            if(pos<=Long) {Num=i;break;}//需要删掉num-1个
        }
        int lst=pos;
        for(int i=1;i<Num;i++)lst-=len-i+1;
        Num--;
        top=0;
        for(int i=1;i<=len;i++){
            while(Num&&top&&s[i]<st[top]){Num--;top--;}
            st[++top]=s[i];
        }
        while(Num){top--;Num--;}
        printf("%c",st[lst]);
    }
    return 0;
}