题解：P16440 [XJTUPC 2026] 公式战士

dongzirui0817 · 2026-05-11 12:29:15 · 题解

注意到除了 a - x 或 a \div x 操作是单调递减的，其他都是单调递增的。

也就是说 a - x 或 a \div x 操作时，要想获得最大值， x 要最小；其他操作要想获得最大值， x 要最大。

而我们最后想获得最大值，所以只要让每一轮的 x 取到最大或最小即可。

所以用 L, R 存最小值和最大值，然后暴力处理通过每一种门后值的变化，并更新 L, R 即可。

时间复杂度 O(\sum n)。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int T, n;
ll x;

ll F(string a, string b, string c, ll p) {
    if (a == "x") {
        ll C = 0;
        for (auto ch : c) C = C * 10 + ch - '0';
        if (b == "+") return p + C;
        if (b == "-") return p - C;
        if (b == "*") return p * C;
        if (b == "/") return p / C;
    }
    ll C = 0;
    for (auto ch : a) C = C * 10 + ch - '0';
    if (b == "+") return C + p;
    if (b == "-") return C - p;
    if (b == "*") return C * p;
    if (b == "/") return C / p;
    return 114514;  // 不会执行 
}

int main() {
    cin >> T;
    for ( ; T-- ; ) {
        cin >> n >> x;
        ll l = x, r = x;
        for (int i = 1 ; i <= n ; i++) {
            string a, b, c, d, e, f;
            cin >> a >> b >> c >> d >> e >> f;
            ll L = l, R = r;
            l = min({F(a, b, c, L), F(a, b, c, R), F(d, e, f, L), F(d, e, f, R)});
            r = max({F(a, b, c, L), F(a, b, c, R), F(d, e, f, L), F(d, e, f, R)});
        }
        cout << r << endl;
    }
    return 0;
}

:::