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

· · 题解

求点赞 qwq！

思路

容易想到的一个贪心，每一步直接计算两个门的结果，选最大的即可。

但是给你一个 hack：

2 5
x + 1 x + 2
100 / x 100 / x

就错了。

因为当前步骤选择大值，后续除法运算可能导致结果更小；反之，当前小值在后面的除法可能得到更大结果。

那简单，每一步维护当前能达到的最大和最小战斗力即可。

代码

单次时间复杂度 O(n)。

其实 f 和 g 可以滚掉。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+1;
int T,n,x,f[N],g[N];
string e1,o,e2,f1,oo,f2;
int cal(int x,string a,string op,string b){
    int num=(a=="x"?stoll(b):stoll(a));
    if(op=="+")return x+num;
    if(op=="-")return (a=="x")?x-num:num-x;
    if(op=="*")return x*num;
    if(op=="/")return (a=="x")?x/num:num/x;
}
void sol(){
    cin>>n>>x,f[0]=g[0]=x;
    for(int i=1;i<=n;i++){
        cin>>e1>>o>>e2>>f1>>oo>>f2,
        f[i]=max({cal(f[i-1],e1,o,e2),cal(g[i-1],e1,o,e2),cal(f[i-1],f1,oo,f2),cal(g[i-1],f1,oo,f2)}),
        g[i]=min({cal(f[i-1],e1,o,e2),cal(g[i-1],e1,o,e2),cal(f[i-1],f1,oo,f2),cal(g[i-1],f1,oo,f2)});
    }
    cout<<f[n]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>T;
    while(T--)sol();
}