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

zhang_kevin · 2026-05-12 12:13:43 · 题解

每次都让 x 尽量大显然不对，因为有除以 x 的操作。

因此不妨维护两个变量 u,v，表示目前 x 的最小值与最大值。

这样经过每扇门时，直接把 u,v 带入两个表达式计算出 4 个值，然后更新 u,v 即可。

最后要求最大值，输出 v 即可，时间复杂度 \mathcal{O}(Tn)。

参考代码：

#include<bits/stdc++.h>
// #define int long long
#define fo(i, l, r) for(decltype((l) + (r)) i = (l); i <= (r); ++i)
#define fd(i, l, r) for(decltype((l) + (r)) i = (l); i >= (r); --i)
#define fu(i, l, r) for(decltype((l) + (r)) i = (l); i <  (r); ++i)
#define y1 zhang_kevin
#define pii pair<int, int>
#define fi first
#define se second
#define vec vector
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ull unsigned long long
#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
using namespace std;
bool ST;
char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf, obuf[1 << 20], *p3 = obuf;
inline char gc(){
    if(p1 == p2){
        p1 = ibuf, p2 = ibuf + fread(ibuf, 1, 1 << 20, stdin);
        if(p1 == p2) return EOF;
        return *p1++;
    }
    return *p1++;
}
inline char pc(char ch){
    if(p3 == obuf + (1 << 20)) flush();
    *p3 = ch;
    return *p3++;
}
template<typename type>
inline int rd(type &x){
    x = 0; bool f = 0; char ch = gc();
    while(!isdigit(ch)) f |= ch == '-', ch = gc();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    return f ? x = -x : 0;
}
template<typename type, typename ...T>
inline void rd(type &x, T &...y){rd(x), rd(y...);}
inline void gs(string &s){
    s.clear(); char c = gc();
    while(c == ' ' || c == '\n' || c == '\t' || c == '\r') c = gc();
    while(c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != EOF) s += c, c = gc();
    return;
}
class Flush{public: ~Flush(){flush();}}___;
template<typename type>
inline void wr(type x){
    if(x < 0) pc('-'), x = -x;
    if(x > 9) wr(x / 10);
    pc(x % 10 + '0');
    return;
}
inline void wrs(const string& s){for(auto ch : s) pc(ch);}
namespace Solution{
    int T, n; ll x;
    inline ll calc(ll a, string op, ll b){
        if(op == "+") return a + b;
        if(op == "-") return a - b;
        if(op == "*") return a * b;
        return a / b;
    }
    inline void Solve(){
        rd(T); while(T--){
            rd(n, x); ll u = x, v = x;
            fo(i, 1, n){
                string fi1, o1, se1, fi2, o2, se2;
                gs(fi1), gs(o1), gs(se1), gs(fi2), gs(o2), gs(se2);
                ll u1, v1, u2, v2;
                if(fi1 == "x"){
                    u1 = calc(u, o1, stoll(se1));
                    v1 = calc(v, o1, stoll(se1));
                }else{
                    u1 = calc(stoll(fi1), o1, u);
                    v1 = calc(stoll(fi1), o1, v);
                }
                if(fi2 == "x"){
                    u2 = calc(u, o2, stoll(se2));
                    v2 = calc(v, o2, stoll(se2));
                }else{
                    u2 = calc(stoll(fi2), o2, u);
                    v2 = calc(stoll(fi2), o2, v);
                }
                u = min({u1, v1, u2, v2});
                v = max({u1, v1, u2, v2});
            }
            wr(v), pc('\n');
        }
        return;
    }
}
bool ED;
signed main(){
    clock_t START = clock();
    // freopen("input.in", "r", stdin), freopen("output.out", "w", stdout);
    Solution::Solve();
    cerr << (double)(clock() - START) / CLOCKS_PER_SEC << " s" << '\n';
    cerr << 1.0 * abs(&ED - &ST) / 1024 / 1024 << " MB" << '\n';
    return 0;
}