2025.9.15 模拟赛

公平合影（fairphoto）

前缀和

首先按照位置从小到大排序。对于站在一段同样类型的同学，我们可以通过一个 $\mathcal{O}(n)$ 的双指针处理轻松解决。对于 $\text{G}$ 和 $\text{H}$ 类型数量相同的一段同学，我们可以令 $\text{G}$ 的值为 $1$、$\text{H}$ 的值为 $-1$，那么一段区间满足条件就等价于和为 $0$。

连续区间和考虑前缀和。令 $p_i=\sum _{j=1}^i{a}_j$，那么如果一个区间 $[l,r]$ 满足条件就有 $p_r-p_{l-1}=0$，也就是 $p_r=p_{l-1}$。当我们枚举 $r$ 时，所有配对的 $l$ 中当然是越小越好，因此我们开一个桶记录最前面一个 $p_i$ 相同的 $i$。

时间复杂度 $\mathcal{O}(n)$。注意负数下标需要通过偏移或者 map 处理。

#include <fstream>
#include <algorithm>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5;
 
ifstream cin("fairphoto.in");
ofstream cout("fairphoto.out");
 
struct Node {
  LL x;
  char c;
} a[kMaxN];
 
LL p[kMaxN], lst[2 * kMaxN], n, ans;
 
LL &at(LL x) {
  return lst[x + kMaxN];
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].c;
  }
  sort(a + 1, a + n + 1, [](auto a, auto b) {
    return a.x < b.x;
  });
  for (LL i = 1, j; i <= n; ) {
    for (j = i; j <= n && a[i].c == a[j].c; j++) { }
    ans = max(ans, a[j - 1].x - a[i].x);
    i = j;
  }
  for (LL i = 1; i <= n; i++) {
    p[i] = p[i - 1] + (a[i].c == 'G') - (a[i].c == 'H');
  }
  fill(begin(lst), end(lst), -1);
  at(p[0]) = 0;
  for (LL i = 1; i <= n; i++) {
    if (at(p[i]) != -1) {
      ans = max(ans, a[i].x - a[at(p[i]) + 1].x);
    }
    if (at(p[i]) == -1) {
      at(p[i]) = i;
    }
  }
  cout << ans << '\n';
  return 0;
}

暗号解码（cipher）

结论

首先字符集大小达到了 $26$，状压很难处理，我们需要找规律。通过猜测，可以找到规律：对于询问字符串 $r$ 中的任意一对字符 $(i,j)$，如果只保留 $s$ 和 $t$ 中 $(i,j)$ 的这两种字符仍然都相等，那么答案就是 $\text{Yes}$。

可以这样子感性证明，就是如果 $(\text{a},\text{b})$ 满足条件，且 $(\text{b},\text{c})$ 满足条件，且 $(\text{a},\text{c})$ 满足条件，那么 $\text{a}$ 相对于 $\text{b}$ 的位置和 $\text{c}$ 相对于 $\text{b}$ 的位置在 $s$ 和 $t$ 中都是一样的，$a$ 相对于 $c$ 的位置在 $s$ 和 $t$ 中也是一样的，所以 $(\text{a},\text{b},\text{c})$ 的相对位置在 $s$ 和 $t$ 中也是一样的。

所以预处理 $(i,j)$ 是否满足条件就行了。时间复杂度 $\mathcal{O}(26^2(n+q))$。

#include <fstream>
#include <cstring>
#include <string>
 
using namespace std;
 
const int kMaxN = 1e5 + 5;
 
ifstream cin("cipher.in");
ofstream cout("cipher.out");
 
int a[kMaxN], b[kMaxN], f[26][26], n, m, q;
char s[kMaxN], t[kMaxN], d[kMaxN];
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  // 以下已更改，非赛事代码
  string temp_s, temp_t;
  cin >> temp_s >> temp_t;
  strcpy(s + 1, temp_s.c_str());
  strcpy(t + 1, temp_t.c_str());
  // 更改结束。为解决 C++17 编译错误
  n = strlen(s + 1);
  m = strlen(t + 1);
  for (int i = 0; i < 26; i++) {
    for (int j = i; j < 26; j++) {
      int c1 = 0, c2 = 0;
      for (int k = 1; k <= n || k <= m; k++) {
        if (k <= n) {
          if (s[k] == i + 'a') {
            a[++c1] = i;
          } else if (s[k] == j + 'a') {
            a[++c1] = j;
          }
        }
        if (k <= m) {
          if (t[k] == i + 'a') {
            b[++c2] = i;
          } else if (t[k] == j + 'a') {
            b[++c2] = j;
          }
        }
      }
      f[i][j] = c1 == c2 && equal(a + 1, a + c1 + 1, b + 1);
    }
  }
  for (cin >> q; q; q--) {
    string temp_d;
    cin >> temp_d;
    strcpy(d + 1, temp_d.c_str());
    int k = strlen(d + 1), ans = 1;
    for (int i = 1; i <= k && ans; i++) {
      for (int j = i; j <= k && ans; j++) {
        ans &= f[d[i] - 'a'][d[j] - 'a'];
      }
    }
    cout << (ans ? 'Y' : 'N');
  }
  return 0;
}

分组（grouping）

CDQ 树状数组 线段树 前缀和

首先对于这种中位数的题目我们已经很有经验了，当然是把大于等于 $x$ 的数变成 $1$，小于 $x$ 的数变成 $-1$。至于和是要大于 $0$ 还是大于等于 $0$ 满足要求要看题目中对于中位数的定义，本题是大于等于 $x$ 的数不比小于 $x$ 的数少，因此是大于等于 $0$。

对处理后的数组做前缀和，枚举右端点 $r$，我们需要找出有多少个左端点 $l$ 满足 $p_r-p_{l-1}\ge 0$，也就是找寻二元组 $(i,j)$ 的数量，满足 $i<j$ 且 $p_i\le p_j$。这是典型的二维偏序，可以使用 CDQ 分治或者树状数组求解。我脑抽了写了个线段树，但是跑得也不慢。注意负数下标，需要通过离散化或者偏移来处理（其实写线段树可以不处理的）。

时间复杂度 $\mathcal{O}(n{\log }_{2}n)$。

#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5;
 
ifstream cin("grouping.in");
ofstream cout("grouping.out");
 
LL a[kMaxN], p[kMaxN], tr[8 * kMaxN], n, x, ans;
 
void modify(LL p, LL l, LL r, LL x) {
  tr[p]++;
  if (l == r) {
    return;
  }
  LL m = (l + r) / 2;
  if (x <= m) {
    modify(2 * p, l, m, x);
  } else {
    modify(2 * p + 1, m + 1, r, x);
  }
}
 
LL query(LL p, LL l, LL r, LL s, LL t) {
  if (s <= l && r <= t) {
    return tr[p];
  }
  LL m = (l + r) / 2, res = 0;
  if (s <= m) {
    res += query(2 * p, l, m, s, t);
  }
  if (m < t) {
    res += query(2 * p + 1, m + 1, r, s, t);
  }
  return res;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> x;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
    p[i] = p[i - 1] + (a[i] >= x) - (a[i] < x);
  }
  modify(1, 0, 2e5, p[0] + 1e5);
  for (LL i = 1; i <= n; i++) {
    ans += query(1, 0, 2e5, 0, p[i] + 1e5);
    modify(1, 0, 2e5, p[i] + 1e5);
  }
  cout << ans << '\n';
  return 0;
}

平衡小径（balance）

点分治 前缀和 分治

本题我采用的是暴力。

首先枚举 $i$ 作为路径的起点，让后把 $i$ 当作根来统计就不用管复杂的带 LCA 的路径了。把黑色变成 $1$，白色变成 $-1$，那么一条路径如果和为 $0$ 就满足黑色数量等于白色的数量。做从 $i$ 开始的树上前缀和。对于一条路径，如果它最底下的前缀和值为 $0$，并且路径上有一个不同于端点的点前缀和值也为 $0$，那么这条路径就满足条件。

时间复杂度 $\mathcal{O}(n^2)$。注意答案最后要除以 $2$。成功获得 $50$ 分。

#include <fstream>
#include <utility>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5;
 
ifstream cin("balance.in");
ofstream cout("balance.out");
 
LL p[kMaxN], n, ans;
vector<pair<LL, LL>> e[kMaxN];
 
void dfs(LL x, LL f) {
  for (auto i : e[x]) {
    if (i.first == f) {
      continue;
    }
    p[i.first] = p[x] + (i.second == 1) - (i.second == 0);
    dfs(i.first, x);
  }
}
 
void solve(LL x, LL f, LL cnt) {
  ans += cnt >= 2 && !p[x];
  for (auto i : e[x]) {
    if (i.first == f) {
      continue;
    }
    solve(i.first, x, cnt + !p[i.first]);
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1, u, v, w; i < n; i++) {
    cin >> u >> v >> w;
    e[u].emplace_back(v, w);
    e[v].emplace_back(u, w);
  }
  for (LL i = 1; i <= n; i++) {
    p[i] = 0;
    dfs(i, 0);
    solve(i, 0, 0);
  }
  cout << ans / 2 << '\n';
  return 0;
}

本题正解是点分治，每次找重心统计过重心的路径，然后把重心删了拆分成多棵树递归求解。最难的是统计路径数量，有点复杂，这里讲不下了。

总结

总分：$100+100+100+50=350$。

今天的比赛还是比较简单的，前三题都非常轻松地写出来了，第一题和第三题都是一眼题，第二题需要猜一下结论（应该也能证明的）。最后一题写出了 $50$ 分的 $\mathcal{O}(n^2)$ 暴力（虽然 $\mathcal{O}(n^3)$ 也能过 $50$ 分，因为随机树高期望 ${\log }_{2}n$ 路径长最多 $2{\log }_{2}n$），但是迫于不会点分治导致无法 AC。所以还是太菜了，高级算法涉及少了。