题解：P11186 三目运算

yummy · 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;
}