题解 | 小红的能量校准

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

using ll = long long;
using i128 = __int128;

int main() {
    string s; cin >> s;
    i128 num = 0, bse = 1;
    while (s.back() != '=') {
        if (s.back() == '-') {
            num = -num;
        }
        else {
            num += bse * (s.back() - '0');
            bse *= 10;
        }
        s.pop_back();
    }
    s.pop_back();
    i128 l = -LLONG_MAX, r = LLONG_MAX;
    while (l < r) {
        i128 mid = (l + r) / 2;
        auto get = [&]() -> i128 {
            vector<char> sign;
            vector<i128> v;
            i128 now = 0;
            char lst = ' ';
            for (int i = 0; i < (int)s.size(); ++i) {
                if (isdigit(s[i])) {
                    if (lst == ')' || lst == 'x') sign.push_back('*');
                    now = now * 10 + s[i] - '0';
                    lst = 'd';
                }
                else if (lst == 'd') {
                    v.push_back(now);
                    now = 0;
                }
                if (s[i] == 'x') {
                    if (lst == ')' || lst == 'd') sign.push_back('*');
                    v.push_back(mid);
                    lst = 'x';
                }
                else if (s[i] == '(') {
                    if (lst == 'd' || lst == 'x' || lst == ')') sign.push_back('*');
                    sign.push_back('(');
                    lst = '(';
                }
                else if (s[i] == '+') {
                    while (!sign.empty() && sign.back() == '*') {
                        i128 a = v.back();
                        v.pop_back();
                        i128 b = v.back();
                        v.pop_back();
                        v.push_back(a * b);
                        sign.pop_back();
                    }
                    sign.push_back('+');
                    lst = '+';
                }
                else if (s[i] == '*') {
                    sign.push_back('*');
                    lst = '*';
                }
                else if (s[i] == ')') {
                    while (sign.back() != '(') {
                        i128 a = v.back();
                        v.pop_back();
                        i128 b = v.back();
                        v.pop_back();
                        if (sign.back() == '*') v.push_back(a * b);
                        else v.push_back(a + b);
                        sign.pop_back();
                    }
                    sign.pop_back();
                    lst = ')';
                }
            }
            if (lst == 'd') v.push_back(now);
            while (!sign.empty()) {
                i128 a = v.back();
                v.pop_back();
                i128 b = v.back();
                v.pop_back();
                if (sign.back() == '*') v.push_back(a * b);
                else v.push_back(a + b);
                sign.pop_back();
            }
            return v.back();
        };
        i128 t = get();
        if (t > num) r = mid - 1;
        else if (t < num) l = mid + 1;
        else l = r = mid;
    }
    cout << (ll)l;
}

写的有点乱，但思路很好想，比较模拟的一道题。

左侧的表达式只有加号和乘号，且题干说明是一次函数，说明左侧一定是单调递增的一次函数，因为x已知时求左侧中缀表达式是比较经典的，考虑二分答案，表达式算出的结果和右面的值比较。

有点恶心的是处理不带乘号的乘法。发现添加乘号的情况是有限的，且只和相邻两数（字符）的组合有关。假设数字为d，有 { ")(", ")d", ")x", "x(", "d(", "xd", "dx" } 几种正常中缀表达式不可能出现的情况，在这几种情况出现时，手动在中间插入乘号即可。

理论上需要处理计算过程中的越界问题，虽然题目说了过程不可能超过abs(LLONG_MAX)，但是只能保证带入x的时候不越界，如果用的是二分的话就不一定了，于是开了__int128。因为题干说结果肯定在long long范围内，所以最后转成long long输出即可。