自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 23:05:03，当前版本为作者最后更新于2024-10-16 11:30:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

C. 三目运算 (expr) 官方题解

本题考察的主要知识点：

• 【4】递归法

建立框架

考虑计算机要求一个 $x$ 对应的值（设表达式的第一个字符为 S[s]），要分为如下几个步骤：

• 检查是否纯数值。（如果表达式无三目运算，则第一个字符 S[s] 一定是数字。）如果是，则直接得到这个数值。
• 分析条件：现在 S[s+1] 是大于或小于号，S[s+2]开始是一个数字。
• 处理条件成立情形：这也是一个分段常数表达式，在条件的数字部分结束后一个字符开始，可以递归处理。
• 处理条件不成立情形：从条件成立情形结束后的位置后一个字符开始，也可以递归处理。
• 返回值：根据 $x$ 所在的分支得到对应的返回值。

我们发现，在函数给表达式求值的同时，还需要记录表达式最后一个字符的位置（否则表达式的另一个分支就不知道从哪里开始）。

然后，“从表达式指定位置开始读取一个数值，然后返回数字结束的位置”也是常用功能，如果使用一个函数简化一下，代码会更清晰。

实现暴力

如果大家有接触过快速读入模板，那么写法是相近的，但是本题不需要处理负数。

下面的函数实现读取 $x$ 的值，然后返回最后一个数字后一个位置的下标。

int m,q;
char S[2000005];
int getint(int s,int &x){
	x=0;
	while(isdigit(S[s])){
		x=x*10+(S[s]^'0');
		s++;
	}
	return s;
}

下面是递归处理表达式的参考写法。

struct result{int val,len;};
result calc(int s,int x){
	if(isdigit(S[s])){
		int tmp;
		int len=getint(s,tmp);
		return {tmp,len};
	}
	int sep;
	int stt=getint(s+2,sep);
	result pos=calc(stt+1,x);
	result neg=calc(pos.len+1,x);
	if(S[s+1]=='>' && x>sep || S[s+1]=='<' && x<sep)
		return {pos.val, neg.len};
	else
		return {neg.val, neg.len};
}

这样 calc 时间复杂度为 $O(|S|)$，因为有 $q$ 次询问，总时间复杂度 $O(|S|q)$。

优化

我们能不能只读取一次表达式，就把所有 $1\sim m+1$ 之内的 $x$ 都求出来呢？（当 $x>m$ 时，显然表达式的值没有区别，因此只要求到 $m+1$ 即可。）

我们发现，对于一个分支嵌套，能进入到某一个分支的 $x$，必然在一个区间内。因此可以把 calc 函数改成 calc(int s,int l,int r)，表示对于所有 $l\le x\le r$，计算表达式的值，并存入全局数组 res 当中。

解析表达式部分的代码比较接近，但是不同之处在于递归。现在每次递归，你需要把 $l\sim r$ 这个区间根据是否符合条件拆成两个小区间分别求值。时间复杂度 $O(|S|+m+q)$。

下面给出参考代码：

#include<bits/stdc++.h>
using namespace std;
int m,q,res[100005];
char S[2000005];
int getint(int s,int &x){
	x=0;
	while(isdigit(S[s])){
		x=x*10+(S[s]^'0');
		s++;
	}
	return s;
}
int calc(int s,int l,int r){
	if(isdigit(S[s])){
		int tmp;
		int ret=getint(s,tmp);
		for(int i=l;i<=r;i++)
			res[i]=tmp;
		return ret;
	}
	int sep;
	int stt=getint(s+2,sep);
	if(S[s+1]=='>'){
		int neg=calc(stt+1,sep+1,r);
		return calc(neg+1,l,sep);
	}
	else{
		int neg=calc(stt+1,l,sep-1);
		return calc(neg+1,sep,r);
	}
}
int main(){
	scanf("%d%d%s",&m,&q,S);
	calc(0,1,m+1);
	for(;q;q--){
		int x;
		scanf("%d",&x);
		printf("%d\n",res[min(x,m+1)]);
	}
	return 0;
}