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

Bc2_Ch1ckenPr1nce · 2026-05-12 14:41:11 · 题解

Solution

可以算一个分类讨论吧。

对于符号为 + 和 \times 的式子：当 x 增大，式子的结果也增大。此时需要保证 x 尽可能大。

对于符号为 - 的式子：

• 若 x 在前面：对于式子 x - k，可以转化为 x + (-k)。当 x 增大，式子的结果也增大。此时需要保证 x 尽可能大。
• 若 x 在后面：对于式子 k - x，可以转化为 -x + k。由于 x 项的系数是 -1。所以，当 x 增大，式子的结果减小。此时需要保证 x 尽可能小。

对于符号为 \div 的式子：

• 若 x 在前面：对于式子 x \div k，可以转化为 \frac{1}{k}x。当 x 增大，式子的结果也增大。此时需要保证 x 尽可能大。
• 若 x 在后面：对于式子 k \div x，此时式子是分式。根据分式的性质，当 x 增大，式子的结果减小。此时需要保证 x 尽可能小。

根据上面的推论，我们得到结论：当过一扇门时，整数 x 总是越大越好或越小越好。

所以，在计算过程中，我们只需要维护当前情况下你可以得到的最大值和最小值。

Code

代码有点难写。

对于字符串处理不熟悉的小朋友可以参考一下。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 2e5 + 10;

ll n, mx[kMaxN], mn[kMaxN];
string n1, op, n2;

ll C(ll x, string n1, string op, string n2) {
  ll del = (n1 == "x"? stoll(n2) : stoll(n1));
  if (op == "+") {
    return x + del;
  } else if (op == "*") {
    return x * del;
  } else if (op == "-") {
    return (n1 == "x"? x - del : del - x);
  } else {
    return (n1 == "x"? x / del : del / x);
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n >> mx[0], mn[0] = mx[0];
    for (int i = 1; i <= n; ++ i) {
      cin >> n1 >> op >> n2;
      mx[i] = max(C(mx[i - 1], n1, op, n2), C(mn[i - 1], n1, op, n2));
      mn[i] = min(C(mx[i - 1], n1, op, n2), C(mn[i - 1], n1, op, n2));
      cin >> n1 >> op >> n2;
      mx[i] = max({mx[i], C(mx[i - 1], n1, op, n2), C(mn[i - 1], n1, op, n2)});
      mn[i] = min({mn[i], C(mx[i - 1], n1, op, n2), C(mn[i - 1], n1, op, n2)});
    }
    cout << mx[n] << '\n';
  }
  return 0;
}