2025-10-14模拟赛总结

liuyi0905 · 2025-10-16 16:13:32 · 生活·游记

前言

唉……直接趋势了。我是zrr，T3都没做出来。

成绩：100 + 100 + 5 + 50。

考这么差也没什么好说的了。

A

签到题。

容易发现，对于第 i 个人，可以到达的温度范围最多为 [l_{i - 1} - \Delta t, r_{i - 1} + \Delta t]，其中 [l_i, r_i] 表示第 i 个人可到达的温度区间，\Delta t 为与前一个人的时间差。

所以可以这样转移：

• l_i \gets \max\{l_{i - 1} - \Delta t, x_i\}
• r_i \gets \min\{r_{i - 1} + \Delta t, y_i\}

最后判断一下每一个 i 是否满足 l_i \le r_i 即可。

还是很简单的，很快就做出来了。

B

也比较简单。

考虑离线，对于每一种遗物都单独处理。容易发现，要找到距离最近的点，就是一直向根节点走，遇到的第一个有目标遗物的点即为答案。

可以这样操作，从上往下遍历树，对于有遗物的点 x，直接将整个以 x 为根的子树的点的权值改为 x。则每个点的最终权值就是离他最近的点。

对于更改子树的权值，有一个结论：每个子树内节点的 dfs 序是连续的。所以将树上问题转化为数组，直接用线段树区间修改即可。

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, q, l[N], r[N], h[N], t[N << 2], v[N << 2], s[N];
vector<int> e[N], g[N];
vector<pair<int, int>> k[N];
void S(int u, int fa) {
  l[u] = ++m, h[u] = h[fa] + 1;
  for (int v : e[u]) v != fa && (S(v, u), 1);
  r[u] = m;
}
void A(int u, int l, int r, int w) {
  v[u] = w, t[u] = (r - l + 1) * w;
}
void D(int u, int l, int r) {
  int o = l + r >> 1;
  v[u] && (A(2 * u, l, o, v[u]), A(2 * u + 1, o + 1, r, v[u]), v[u] = 0);
}
void U(int u, int l, int r, int x, int y, int w) {
  if (l > y || r < x) return;
  if (l >= x && r <= y) return A(u, l, r, w);
  int o = l + r >> 1;
  D(u, l, r), U(2 * u, l, o, x, y, w), U(2 * u + 1, o + 1, r, x, y, w), t[u] = t[2 * u] + t[2 * u + 1];
}
int Q(int u, int l, int r, int x) {
  if (l > x || r < x) return 0;
  if (l == x && r == x) return t[u];
  int o = l + r >> 1;
  return D(u, l, r), Q(2 * u, l, o, x) + Q(2 * u + 1, o + 1, r, x);
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 2, x; i <= n; i++)
    cin >> x, e[x].push_back(i), e[i].push_back(x);
  for (int i = 1, k; i <= n; i++) {
    cin >> k;
    for (int x; k; k--) cin >> x, g[x].push_back(i);
  }
  S(1, 0);
  for (int i = 1; i <= n; i++)
    sort(g[i].begin(), g[i].end(), [](int x, int y) { return h[x] < h[y]; });
  cin >> q;
  for (int i = 1, x, y; i <= q; i++)
    cin >> x >> y, k[y].push_back({x, i});
  for (int i = 1; i <= n; i++) {
    U(1, 1, n, 1, n, -1);
    for (int x : g[i]) U(1, 1, n, l[x], r[x], x);
    for (auto [x, p] : k[i]) s[p] = Q(1, 1, n, l[x]);
  }
  for (int i = 1; i <= q; i++) cout << s[i] << "\n";
  return 0;
}

::::

C

根本不会好吧，太菜了😭😭😭

直接输出的 -1，居然有 5 分😥

D

也根本不会啊，只好打了 \mathcal{O}(n ^ 2) 暴力。

设 f_i 表示 i 到叶节点的最小代价，方程为：