C. Decreasing String -思维 + 单调栈

题面

分析:

赛时想到了二分用二分找字符串位置，一直WA2，补题。
可以通过单调栈维护每次删去哪个字符，以及字符该不该删去，记录每一次在后面加上的字符串的大小，可以发现每次字符串大小减一，用数组存字符串中最小的字典序，一旦数组中字符大于当前遍历字符，就弹出最后字符，弹出字符也就意味着进行了一次删除，此时需要将$pos$更新，减去当前字符串大小，并且当前字符串大小减一，直到$pos$小于当前字符串大小。需要在字符串末尾加上一个小于任何字符的字符，因为可能出现某次操作后字典与已经是最小不需要再进行删除，那么就需要在字符串末尾进行删除直到满足$pos$的范围。

代码：

#include 

using namespace std;
using ll = long long;

void solve() {
    string s;
    cin >> s;
    ll n;
    cin >> n;
    n --;
    int cnt = s.size();
    bool ok = n < s.size();
    s += 1;
    vector<char> ans;
    for(int i = 0; i < s.size(); i ++) {
        while(!ok && ans.size() > 0 && ans.back() > s[i]) {
            n -= cnt;
            cnt --;
            ans.pop_back();
            if(n < cnt) ok = true;
        }
        ans.push_back(s[i]);
    }
    cout << ans[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T --) {
        solve();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37