C. Decreasing String
分析:暴力做法是很容易想到的,但时间复杂度为O(n2)
这是我打cf以来看到的最好的题解。
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>#define inf 0x3f3f3f3f
#define int long long
const int N =2e5 + 10;
//#include <bits/stdc++.h>
typedef long long ll;
#include<iostream>
using namespace std;//long long MAX(long long a, long long b) { return a < b ? b : a; }signed main() {int T; cin >> T;while (T--) {string s; cin >> s;int pos; cin >> pos;pos--;//处理完可以直接s[pos]这样访问int curLen = s.size();bool f = pos < curLen;//如果为true,就不用再删了s.push_back('a' - 1);vector<char> st;for (auto c : s) {if (!st.size()) {st.push_back(c);continue;}while (!f && c < st.back()) {st.pop_back();//每删一次就代表操作了一次,pos要减去当前长度pos -= curLen;curLen--;if (pos < curLen) f = true;}st.push_back(c);}cout << st[pos];}return 0;
}