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

nyt_nyt2012 · 2026-05-10 19:15:34 · 题解

这题挺坑的，赛时吃一罚。\ \ 首先想到简单贪心：每次进门都选结构最大的，然后发现样例过不去。所以这个贪心是错误的，考虑进一步思考。\ \ 通过观察样例，我们发现会有 d\div x 和 d-x 的情况，这时只用上一步最大值可能这一步结果取不到最大值。不过不难发现这两种情况都会在 x 取最小值时结果最大。所以我们考虑维护这两个最值，运算是将这两个值分别代入两边的式子算即可。不开 long long 见祖宗。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,t,n;string s[11000][7];
int tomath(string s){
    int ans=0;
    for(int i=0;i<s.size();i++){
        ans=ans*10+s[i]-'0';
    }
    return ans;
}
int suan(int i,int op,int x){
    if(op==1){
        if(s[i][1]=="x"){
            int e=tomath(s[i][3]);
            if(s[i][2]=="+")x=x+e;
            if(s[i][2]=="-")x=x-e;
            if(s[i][2]=="*")x=x*e;
            if(s[i][2]=="/")x=x/e;
        }
        else{
            int e=tomath(s[i][1]);
            if(s[i][2]=="+")x=x+e;
            if(s[i][2]=="-")x=e-x;
            if(s[i][2]=="*")x=x*e;
            if(s[i][2]=="/")x=e/x;
        }
    }
    else{
        if(s[i][4]=="x"){
            int e=tomath(s[i][6]);
            if(s[i][5]=="+")x=x+e;
            if(s[i][5]=="-")x=x-e;
            if(s[i][5]=="*")x=x*e;
            if(s[i][5]=="/")x=x/e;
        }
        else{
            int e=tomath(s[i][4]);
            if(s[i][5]=="+")x=x+e;
            if(s[i][5]=="-")x=e-x;
            if(s[i][5]=="*")x=x*e;
            if(s[i][5]=="/")x=e/x;
        }
    }
    return x;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>x;
        int xmax=x,xmin=x;
        for(int i=1;i<=n;i++){
            cin>>s[i][1]>>s[i][2]>>s[i][3]>>s[i][4]>>s[i][5]>>s[i][6];//全用字符串以减少输入代码复杂度
        }
        for(int i=1;i<=n;i++){
            int xxmax=xmax,xxmin=xmin;//注意这里不能直接算，不然算 xmin 的时候 xmax 已改变
            xmax=max(max(suan(i,1,xxmax),suan(i,2,xxmax)),max(suan(i,1,xxmin),suan(i,2,xxmin)));  xmin=min(min(suan(i,1,xxmax),suan(i,2,xxmax)),min(suan(i,1,xxmin),suan(i,2,xxmin)));
        }
        cout<<xmax<<"\n";
    }
    return 0;
}