灵茶 2023 - 12 - 13

链接 :?

Problem - C - Codeforces

思路 :?

模拟 + 单调栈

先判断 pos 属于第几次变化后的串 s[j]，这个可以用循环模拟来求,但是0x3f是解方程来求的，再判断是是s[j]中的第几个字符；

这样在判断完成之后就可以用单调栈来模拟实现了;

代码 :

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;

using namespace std;

string s ; 
LL p ;

inline void solve(){
	cin >> s ; 
	cin >> p;
	p--;
	int n = s.size();
	// 判断是第几个串  : 第一个串的长度为n,后面n-1,n-2,...,1;
	int t = n;
	while(p>=t){
		p -= t;
		t -= 1;
	}  
	// t : 串的长度 , p : 余数 
	int x = n - t ; // 弄了多少次
	string ys;
	for(auto c : s){
		while(x>0 && !ys.empty() && c <ys.back()){
			ys.pop_back();
			x --;
		}		
		ys += c; 
	}
	cout << ys[p] ;
}
 
signed main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}