2025-10-16模拟赛总结

· · 生活·游记

前言

最惨的一次……呜呜呜😱😱😱

考的实在是太好了

成绩高达 10 + 30 + 30 + 10 = 80 😣

我的 4 倍都没有某些巨佬高😫

A

zrr 题。这个人没有处理剩下的 ?，喜挂 90 分。绝对是 SPJ 的问题，题目里都没有说不能留 ? 🙁

很容易发现一种最优策略：

  1. 先将原有已经匹配的左右括号抵消。
  2. 对于 ?，若左边有多余的 (，则将 ? 改为 )，抵消；若没有，则看右边是否有多余的 )，有的话将 ? 改为 (，抵消。
  3. 将剩余的 ? 按 ()()() 的方式赋值，若数量是奇数，则剩下的那个 ? 随便改。

直接模拟即可。

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int _, n, m, k[N];
bool f[N];
string s;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> _; _; _--) {
    cin >> n >> s, s = " " + s, k[0] = 0, m = n;
    fill(f + 1, f + n + 1, 0);
    for (int i = 1; i <= n; i++)
      s[i] == '(' ? k[++k[0]] = i : s[i] == ')' && k[0] && (f[i] = f[k[k[0]--]] = 1, m -= 2);
    k[0] = 0;
    for (int i = 1; i <= n; i++)
      !f[i] && (s[i] == '(' ? k[++k[0]] = i : (s[i] == ')' ? k[0] && (f[i] = f[k[k[0]--]] = 1, m -= 2) : k[0] && (f[i] = f[k[k[0]--]] = 1, s[i] = ')', m -= 2)));
    k[0] = 0;
    for (int i = n; i; i--)
      !f[i] && (s[i] == ')' ? k[++k[0]] = i : (s[i] == '(' ? k[0] && (k[0]--, m -= 2) : k[0] && (s[i] = '(', k[0]--, m -= 2)));
    k[0] = 0;
    for (int i = 1; i <= n; i++)
      s[i] == '?' && (k[0] ? s[k[k[0]--]] = '(', s[i] = ')', m -= 2 : k[++k[0]] = i);
    for (int i = 1; i <= n; i++)
      s[i] == '?' && (s[i] = '(');
    cout << m << "\n" << s.substr(1) << "\n";
  }
  return 0;
}

::::

B

直接状压，f_i 表示已经选了的字符串状态为 i 的合法前缀数量。可是不知道为什么我写的状压 WA 了，只有 30 分，改成了某些巨佬的写法才 A。

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, k[N], r[N], v, f[1 << N];
unordered_map<int, int> d[N];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (char c : s) {
      r[i] = min(r[i], k[i] += (c == '(') - (c == ')'));
      k[i] <= r[i] && (d[i][k[i]]++);
    }
  }
  for (int i = 1; i < (1 << n); i++) {
    int s = 0;
    for (int j = 0; j < n; j++)
      (i >> j) & 1 && (s += k[j]);
    f[i] = -1;
    for (int j = 0; j < n; j++)
      if ((i >> j) & 1 && ~f[i ^ (1 << j)]) {
        int h = s - k[j], w;
        h >= 0 && (v = max(v, w = f[i ^ (1 << j)] + d[j][-h]), r[j] + h >= 0 && (f[i] = max(f[i], w)));        
      }
  }
  cout << v;
  return 0;
}

::::

C

最后 5 分钟打的暴力，拼尽全力无法战胜了😦

D

暴推 2.5h 公式无果，结果最后 40 分暴力都没有调出来🙄

生无可恋了……

后记

这次终于也是考了一次倒数了啊啊啊啊