dfs24ptsWA求调(马蜂良好)玄关
  • 板块P11186 三目运算
  • 楼主Rt__
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/14 09:42
  • 上次更新2024/10/14 10:15:05
查看原帖
dfs24ptsWA求调(马蜂良好)玄关
757715
Rt__楼主2024/10/14 09:42
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll

int num(string s){
	ll sizee = s.size();
	s = ' ' + s;
	int res = 0;
	for(int i = 1; i <= sizee; i ++){
		res = ((int)s[i] - (int)'0') + res * 10;
	}
	return res;
}
string s;
ll n;
struct ii{
	int l;
	string w;
	bool operator<(const ii & a)const{
		return l < a.l;
	}
};
set<ii>ans;
int dfs(int sta, int l, int r){
	bool bs;
	if(s[sta + 1] == '<')bs = 0;
	else bs = 1;
	int l_num = sta + 2, r_num;
	for(r_num = l_num; r_num; r_num ++){
		if(!(s[r_num] >= '0' && s[r_num] <= '9')){
			r_num --;
			break;
		}
	}
	int nn = num(s.substr(l_num, r_num - l_num + 1));
	int ne_l = l, ne_r = r, nee_l = l, nee_r = r;
	if(bs)ne_l = max(nn + 1, ne_l), nee_r = ne_l - 1;
	else ne_r = min(nn - 1, ne_r), nee_l = ne_r + 1;
	int hou;
	if(s[r_num + 2] == 'x'){
		hou = dfs(r_num + 2, ne_l, ne_r);
	}
	else{
		l_num = r_num + 2;
		for(r_num = l_num; r_num <= n; r_num ++){
			if(!(s[r_num] >= '0' && s[r_num] <= '9')){
				r_num --;
				break;
			}
		}
		ans.insert({ne_r, s.substr(l_num, r_num - l_num + 1)});
      //右端点放在集合中以便查询时直接lower_bound
		hou = r_num;
	}
	int en;
	if(s[hou + 2] == 'x'){
		en = dfs(hou + 2, nee_l, nee_r);
	}
	else{
		l_num = hou + 2;
		for(r_num = l_num; r_num <= n; r_num ++){
			if(!(s[r_num] >= '0' && s[r_num] <= '9')){
				r_num --;
				break;
			}
		}
		ans.insert({nee_r, s.substr(l_num, r_num - l_num + 1)});
		//cout << nee_l << ' ' << nee_r << ' ' << num(s.substr(l_num, r_num - l_num + 1)) << endl;
		en = r_num;
	}
	return en;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
//	freopen("expr3.in", "r", stdin);
//	freopen("expr3.out", "w", stdout);
	int m, q;
	cin >> m >> q;
	cin >> s;
	n = s.size();
	s = ' ' + s;
	if(s[1] != 'x'){
		int x;
		for(int i = 1; i <= q; i++)cin >> x,cout << s;
		return 0;
	}
	dfs(1, 0, m);
	for(int i = 1; i <= q; i ++){
		int x;
		cin >> x;
		x = min(x, m);
		auto it = ans.lower_bound({x, ""});
		ii mid = *it;
		cout << mid.w << endl;
	}
	return 0;
}
2024/10/14 09:42
加载中...