P1695题解

hccan1101 · 2025-10-29 19:37:44 · 题解

题目传送门

思路

这不就纯模拟。\ 我们可以从两个方向来推理车流量范围：

1. 正向推理：从起点到终点，模拟车流量的变化。
2. 反向推理：从终点到起点，反向推导车流量。

然后将两个方向的结果结合起来，得到最准确的范围。

代码

复杂度 O(n) ，数据随便过。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 1e18;
const int N = 111;

struct node{
    int l, r;
};

node add(node a, node b){
    return {a.l + b.l, a.r + b.r};
}

node sub(node a, node b){
    return {a.l - b.r, a.r - b.l};
}

node inter(node a, node b){
    return {max(a.l, b.l), min(a.r, b.r)};
}

string op[N];
node val[N], fw[N], bw[N];

signed main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> op[i] >> val[i].l >> val[i].r;
    }

    // 正向处理
    fw[0] = {0, INF};
    for(int i = 1; i <= n; i++){
        if(op[i] == "on")
            fw[i] = add(fw[i-1], val[i]);
        else if(op[i] == "off")
            fw[i] = sub(fw[i-1], val[i]);
        else
            fw[i] = inter(fw[i-1], val[i]);
    }

    // 反向处理
    bw[n+1] = {0, INF};
    for(int i = n; i >= 1; i--){
        if(op[i] == "on")
            bw[i] = sub(bw[i+1], val[i]);
        else if(op[i] == "off")
            bw[i] = add(bw[i+1], val[i]);
        else
            bw[i] = inter(bw[i+1], val[i]);
    }

    node st = inter(fw[0], bw[1]);
    node ed = inter(fw[n], bw[n+1]);

    cout << st.l << " " << st.r << endl;
    cout << ed.l << " " << ed.r << endl;

    return 0;
}