2025.10.16 模拟赛

密文板

这题看起来就很像贪心构造答案。

首先我们把可以匹配的左右括号都先匹配上，具体思路是从左往右枚举，对于每个右括号，如果左边有还没有匹配的左括号，那么就匹配上。

接下来考虑一个问号和一个括号匹配。一种是问号和右括号匹配。由于和上面进行初始匹配一样都需要枚举右括号，所以可以一起处理。然后是左括号和问号匹配，正着或反着枚举均可，但是正着枚举必须选大于当前下标的最小下标的问号，反着则不需要。

由于我们有些左括号已经在之前跟右括号匹配了，而这里和问号匹配当然是越靠左越好。所以最开始我们找和右括号匹配的左括号需要优先选下标更大的（栈实现），这样才使得在可以留下左括号的情况下，左括号都尽量靠左，可以与更多右边的问号匹配。

最后是剩下的问号自己和自己匹配。按照下标从小到大的顺序一左一右即可。

维护所有的问号我是用了 set。可以快速找小于/大于某个下标的问号，并且支持删除。时间复杂度 $O (n lo g_{2} n)$ 。

#include <fstream>
#include <stack>
#include <set>
 
using namespace std;
 
const int kMaxN = 1e5 + 5;
 
ifstream cin("cipher.in");
ofstream cout("cipher.out");
 
int f[kMaxN], t, n;
set<int> s;
stack<int> q;
char a[kMaxN];
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> a;
    for (int i = n; i >= 1; i--) {
      a[i] = a[i - 1];
    }
    fill(f + 1, f + n + 1, 0);
    for (; q.size(); q.pop()) { }
    s.clear();
    int ans = 0;
    for (int i = 1; i <= n; i++) {
      if (a[i] == '?') {
        s.insert(i);
      }
    }
    for (int i = 1; i <= n; i++) {
      if (a[i] == '(') {
        q.push(i);
      } else if (a[i] == ')') {
        if (q.size()) {
          f[q.top()] = f[i] = 1;
          q.pop();
          ans++;
          continue;
        }
        auto p = s.lower_bound(i);
        if (p != s.begin()) {
          p--;
          f[*p] = f[i] = 1;
          a[*p] = '(';
          s.erase(p);
          ans++;
        }
      }
    }
    for (int i = n; i >= 1; i--) {
      if (a[i] == '(' && !f[i]) {
        auto p = s.upper_bound(i);
        if (p != s.end()) {
          s.erase(p);
          a[*p] = ')';
          ans++;
        }
      }
    }
    bool b = 1;
    for (int i : s) {
      a[i] = b ? '(' : ')';
      ans += !b;
      b ^= 1;
    }
    cout << n - 2 * ans << '\n' << (a + 1) << '\n';
  }
  return 0;
}

括号序列

状压dp 二分前缀和

首先看到 $n \leq 20$ ，这很有可能是状压的题目。然后再看到括号序列，那我们就可以构建一个前缀和数组，左括号减一右括号加一，对于一段前缀和都不小于 $0$ 的前缀，有多少个 $0$ 就代表着有多少个合法括号串前缀。

然后我就设计出了状态： $d p_{i, j}$ 表示若 $n$ 个串的已选状态为 $i$ ，最后的前缀值为 $j$ 所能获得的最大答案。当时我觉得这个状态会炸，因为 $j$ 的取值特别多，但是实际上 $j$ 只有一种取值，即 $i$ 包含的所有 $s_{i}$ 的前缀和值相加的和。不过我赛时还是写了个 map 就是了。

枚举已选状态 $i$ 之后，再枚举新的要选的 $j$ 。如何判断拼上 $j$ 了之后是否存在一段前缀和小于 $0$ 呢？可以对每个串的前缀和值再做一个前缀 $min$ ，这样就可以快速判断整个串。如果整个串拼上来不会导致有小于 $0$ 的，那么就可以直接转移 dp。

对于有小于 $0$ 的，拼完这一段继续拼任何东西都不会有任何加成了。所以我们通过那个前缀 $min$ 的数组做二分，找到最大的 $p$ 使得前 $p$ 个数都不会导致前缀值变到负数。二分完我们还需要求一个前缀当中有多少个指定的数。每个字符串开 $2 \times ∣ s_{i} ∣ + 1$ 个 vector 存前缀值所对应的下标（要加偏移量应对负数），在下标 vector 上二分即可。

时间复杂度 $O (2^{n} (n + i = 1 \sum n lo g ∣ s_{i} ∣))$ 。当然我瞎写了 map 常数较大。

[!] 注意查询一定要判越界，这就是我在初测是挂 $60$ 分的原因。
[c] 一个悲伤的故事是，由于我把 <fstream> 的 f 写成了大写 F 直接导致我这题在 Linux 上 CE 保灵。警钟长鸣🔔

#include <fstream>  // 不要写成 Fstream
#include <algorithm>
#include <vector>
#include <map>
 
using namespace std;
 
const int kMaxN = 21;
 
ifstream cin("seq.in");
ofstream cout("seq.out");
 
int n, ans;
string s[kMaxN];
vector<int> p[kMaxN], m[kMaxN];
vector<vector<int>> v[kMaxN];
map<int, int> dp[1 << kMaxN];
 
vector<int> &get(int i, int j) {
  static vector<int> empty;
  if (j + s[i].size() < 0 || j + s[i].size() >= v[i].size()) {  // 越界
    return empty;
  }
  return v[i][j + s[i].size()];
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    int pre = 0, mn = 1e9;
    p[i].reserve(s[i].size());
    m[i].reserve(s[i].size());
    v[i].resize(2 * s[i].size() + 1);
    for (int j = 0; j < s[i].size(); j++) {
      pre += (s[i][j] == '(' ? 1 : -1);
      mn = min(mn, pre);
      p[i].push_back(pre);
      m[i].push_back(mn);
      get(i, pre).push_back(j);
    }
  }
  dp[0][0] = 0;
  for (int i = 0; i < (1 << n); i++) {
    for (const auto &j : dp[i]) {
      for (int k = 1; k <= n; k++) {
        if (i & (1 << (k - 1))) {
          continue;
        }
        if (j.first + m[k].back() >= 0) {
          int &x = dp[i | (1 << (k - 1))][j.first + p[k].back()];
          int val = j.second + get(k, -j.first).size();
          x = max(x, val);
          ans = max(ans, val);
          continue;
        }
        int p = -1;
        for (int l = 0, r = s[k].size() - 1; l <= r; ) {
          int mid = (l + r) / 2;
          if (j.first + m[k][mid] >= 0) {
            p = mid;
            l = mid + 1;
          } else {
            r = mid - 1;
          }
        }
        if (p != -1) {
          auto x = get(k, -j.first);
          int val = upper_bound(x.begin(), x.end(), p) - x.begin();
          ans = max<int>(ans, j.second + val);
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

法国

暴力数学

记 $a = a tt, b = h p, A = A tt, B = H p$ .

首先我们看到这个式子 $i = 1 \sum k ⌈ \frac{b _{i}}{A _{q}} ⌉ a_{i} \geq B_{q}$ 。我靠，怎么这么复杂，而且随着 $q$ 的增大， $A_{q}$ 会增大，这个分数会变小这也太难维护了吧？但是仔细想想，分子 $b_{i}$ 是固定的，分母单调递增，而一个数 $x$ 除以任意正数（上或下取整均可），不同的答案它的量级貌似是 $O (x)$ 级别的（实测 $x = 3 \times 1 0^{5}$ 时大约有 $1000$ 个），所以我们只需要在分数 $⌈ \frac{b _{i}}{A _{q}} ⌉$ 的值发生变化是重新计算贡献即可。这样子时间复杂度就是 $O (n V)$ 的了，完全可行。

现在我们考虑当 $A_{q}$ 增大到多少的时候分数值会发生改变，即解关于 $x$ 的方程 $⌈ \frac{a}{x} ⌉ < b$ 。根据赤石的推导，可以得到 $x \geq ⌈ \frac{a}{b - 1} ⌉$ ，这里 $a = b_{i}, b = ⌈ \frac{b _{i}}{A _{q}} ⌉$ 。所以当到后面最小的满足 $A_{q} \geq x$ 的地方，分数值才会改变。

由于本题值域只有 $3 \times 1 0^{5}$ ，所以我们直接把 $x$ 当下标，将 $i$ 的值存到 vector 里面。再维护一个指针 $k$ 用来遍历重构，每次把 $k$ 移动到 $\leq A_{q}$ 的所有值上，从 vector 里面取出下标重新计算贡献，计算完之后再算出下一次重算贡献需要的 $A_{q}$ 值。由于每个元素重算贡献的时间复杂度为 $V$ ，所以复杂度满足要求。

注意当分数值已经等于 $1$ 的时候就不要放进 vector 里面了，一个是它的值不会改变（一直都是 $1$ ），一个是计算需要除以它 $- 1$ 的值，直接导致 RE。

#include <fstream>
#include <vector>
#include <queue>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 3e5 + 5;
 
ifstream cin("france.in");
ofstream cout("france.out");
 
LL a1[kMaxN], b1[kMaxN], a2[kMaxN], b2[kMaxN], f[kMaxN], n, m, v, sum;
vector<int> vct[kMaxN];
priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, greater<>> q;
 
LL ceil(LL a, LL b) {
  return (a + b - 1) / b;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> v;
  for (LL i = 1; i <= n; i++) {
    cin >> a1[i] >> b1[i];
  }
  for (LL i = 1; i <= m; i++) {
    cin >> a2[i] >> b2[i];
  }
  for (LL i = 1, j = 1, k = 1; i <= m; i++) {
    for (; k <= a2[i]; k++) {
      for (int j : vct[k]) {
        sum -= f[j];
        LL x = ceil(b1[j], a2[i]);
        sum += x * a1[j];
        f[j] = x * a1[j];
        if (x > 1) {
          vct[ceil(b1[j], x - 1)].push_back(j);
        }
      }
      vct[k].clear();
      vct[k].shrink_to_fit();  // 清内存
    }
    for (; j <= n && sum < b2[i]; j++) {
      LL x = ceil(b1[j], a2[i]);
      sum += x * a1[j];
      f[j] = x * a1[j];
      if (x > 1) {
        vct[ceil(b1[j], x - 1)].push_back(j);  // 大于它 整除值就会改变
      }
    }
    cout << (sum >= b2[i] ? j - 1 : -1) << '\n';
  }
  return 0;
}

酒杯

组合数学概率与期望

赛时我两种暴力都 WA 了，都没有调出来，太悲惨了。

首先是对于 $n, m \leq 500$ ，考虑 $n m^{2}$ 的 DP。设 $d p_{i, j}$ 表示前 $i$ 层已经有了 $j$ 个 AC，那么枚举下一层有了 $k$ 个 AC 计算概率转移即可。注意答案需要额外乘上 $m!$ 因为 $m$ 个 AC 位置可以互换。

对于 $n \leq 20$ 但 $m$ 特别大的数据，考虑枚举有哪几层没有任何一个 AC，计算概率后加起来，再用 $1$ 减去他们，得到任意一层都有 AC 的概率。

Haokee Note

Explorer

2025.10.16 模拟赛

密文板

括号序列

法国

酒杯

Graph View

Table of Contents