2025.10.14 模拟赛

好冷好热好冷好热

首先可以想到很显然的解法，就是设计状态 $(i, j)$ 表示如果第 $i$ 秒温度为 $j$ ，前 $i$ 秒是否均满足条件。当然这个是会炸掉的。

不难发现后面的 $j$ 实际上可取的值是一个区间（所有人的温度要求的交和可能的温度的交）。所以我们只需要维护区间就行了。

但是枚举 $i$ 还是会炸。所以考虑对时间进行离散化，离散化之后就只需要枚举最多 $n$ 个 $i$ 。如果当前 $i$ 与上一个 $i$ 的差值为 $Δ i$ ，那么区间就变成 $[l - Δ i, r + Δ i]$ 。再对当前 $i$ 对应的所有要求温度区间取交集即可。如果取完变空集就不满足条件。

#include <fstream>
#include <algorithm>
#include <utility>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5;
 
ifstream cin("temp.in");
ofstream cout("temp.out");
 
LL l[kMaxN], h[kMaxN], t[kMaxN], val[kMaxN], T, n, m, k;
vector<pair<LL, LL>> v[kMaxN];
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> T; T; T--) {
    cin >> n >> m;
    fill(v + 1, v + k + 1, vector<pair<LL, LL>>());
    k = 0;
    for (LL i = 1; i <= n; i++) {
      cin >> t[i] >> l[i] >> h[i];
      val[++k] = t[i];
    }
    sort(val + 1, val + k + 1);
    k = unique(val + 1, val + k + 1) - val - 1;
    for (LL i = 1; i <= n; i++) {
      t[i] = lower_bound(val + 1, val + k + 1, t[i]) - val;
      v[t[i]].emplace_back(l[i], h[i]);
    }
    []() {
      LL l = m, r = m;
      for (LL i = 1; i <= k; i++) {
        l -= val[i] - val[i - 1];
        r += val[i] - val[i - 1];
        for (const auto &j : v[i]) {
          if (r < j.first || l > j.second) {
            cout << "NO\n";
            return;
          }
          l = max(l, j.first);
          r = min(r, j.second);
        }
        if (l > r) {
          cout << "NO\n";
        }
      }
      cout << "YES\n";
    }();
  }
  return 0;
}

杀戮尖塔

线段树二分倍增树链剖分

首先这道题目有多个不同的遗物，以区间或路径为基础很难处理这些不同的遗物。所以考虑分遗物处理区间。

对于 $x$ 到 $1$ 的路径，很显然我们可以写一个二分，二分出最下方一个点 $i$ 使得 $i \sim x$ 的路径上正好有一个遗物，开 $n$ 棵动态开点线段树用于判断。当然，预处理倍增父亲后直接倍增就行了。

这样子是不好做的，因为我们无法快速查询 $x$ 到 $x$ 上方的祖先之间是否有 $y$ 存在。考虑做树剖，先把 $x$ 往上跳若干条没有 $y$ 存在的链，然后在剩下的那条有 $y$ 的链上做二分或者倍增。时间复杂度 $O (q lo g^{2} n)$ 。

这样子的在线做法的时间复杂度还是太高了。考虑离线，对于每个 $i$ 可能作为哪些 $x$ 的答案。不难发现每个 $i$ 可能给 $i$ 子树中的任意点做贡献，但是对于 $x$ 它要求深度最大的 $i$ 。所以按照深度枚举 $i$ 然后对指定线段树上 $i$ 进行子树覆盖即可。时间复杂度 $O ((q + n) lo g_{2} n)$ 。

当然我写的在线做法。

#include <fstream>
#include <vector>
 
using namespace std;
 
const int kMaxN = 1e5 + 5, kLog = 20;
 
ifstream cin("slay.in");
ofstream cout("slay.out");
 
struct Node {
  int lc, rc, sum;
} tr[kLog * kMaxN];
 
int rt[kMaxN], fa[kMaxN], dp[kMaxN][kLog], dfn[kMaxN], top[kMaxN], dep[kMaxN], siz[kMaxN], son[kMaxN], n, q, cnt, tim;
vector<int> e[kMaxN];
 
void modify(int &p, int l, int r, int x) {
  if (!p) {
    p = ++cnt;
  }
  tr[p].sum = 1;
  if (l == r) {
    return;
  }
  int m = (l + r) / 2;
  if (x <= m) {
    modify(tr[p].lc, l, m, x);
  } else {
    modify(tr[p].rc, m + 1, r, x);
  }
}
 
int query(int p, int l, int r, int s, int t) {
  if (!p || s > t) {
    return 0;
  }
  if (s <= l && r <= t) {
    return tr[p].sum;
  }
  int m = (l + r) / 2, res = 0;
  if (s <= m) {
    res |= query(tr[p].lc, l, m, s, t);
  }
  if (m < t) {
    res |= query(tr[p].rc, m + 1, r, s, t);
  }
  return res;
}
 
void dfs1(int x, int f) {
  dep[x] = dep[f] + 1;
  fa[x] = f;
  siz[x] = 1;
  dp[x][0] = f;
  for (int i = 1; i < kLog; i++) {
    dp[x][i] = dp[dp[x][i - 1]][i - 1];
  }
  for (int i : e[x]) {
    if (i == f) {
      continue;
    }
    dfs1(i, x);
    siz[x] += siz[i];
    if (siz[i] > siz[son[x]]) {
      son[x] = i;
    }
  }
}
 
void dfs2(int x, int t) {
  top[x] = t;
  dfn[x] = ++tim;
  if (son[x]) {
    dfs2(son[x], t);
  }
  for (int i : e[x]) {
    if (i == fa[x] || i == son[x]) {
      continue;
    }
    dfs2(i, i);
  }
}
 
int jump(int x, int y) {
  for (int i = 0; i < kLog; i++) {
    if (y & (1 << i)) {
      x = dp[x][i];
    }
  }
  return x;
}
 
int query(int x, int y) {
  for (; x && !query(rt[y], 1, n, dfn[top[x]], dfn[x]); x = fa[top[x]]) { }
  if (!x) {
    return -1;
  }
  int res = 0;
  for (int l = 0, r = dep[x] - 1; l <= r; ) {
    int m = (l + r) / 2, p = jump(x, m);
    if (query(rt[y], 1, n, dfn[p], dfn[x])) {
      res = p;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  return res;
}
 
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);
  }
  dfs1(1, 0);
  dfs2(1, 1);
  for (int i = 1, k; i <= n; i++) {
    cin >> k;
    for (int x; k; k--) {
      cin >> x;
      modify(rt[x], 1, n, dfn[i]);
    }
  }
  cin >> q;
  for (int x, y; q; q--) {
    cin >> x >> y;
    cout << query(x, y) << '\n';
  }
  return 0;
}

故障机器人

广度优先搜索

首先机器人在路径长度超过 $d$ 之后会炸掉，炸掉后对人没有影响，但是人只要被任意一个机器人的任意一种走法抓住就会死掉，所以我们直接规定所有机器人都不能炸掉就行了（保证每个机器人路径长度始终小于等于 $d$ ）。

我们需要判断如果在 $t$ 时刻到 $i$ 点的话是否又被机器人抓到的可能性，如果有就不能在这个时刻走到 $i$ 。具体来说，如果 $k$ 个机器人当中有任何一个可以正好在 $t$ 时刻到 $i$ ， $i$ 就走不了。

然而，机器人可以在两个点之间反复横跳（如果已走步数小于 $d$ 的话）。所以，我们只需要判断机器人是否有走到 $i$ 的路径且这个路径长与 $t$ 同奇偶，如果还路径长小于等于 $t$ 的话，就是可以走到 $i$ 的。（如果 $t$ 超出了 $d$ ，就把 $t$ 变成小于等于 $d$ 且和 $t$ 同奇偶的数）这是奇偶最短路的模板。

现在我们的主要问题就是对于 $k$ 个怪物跑单源最短路太慢了。不过我们只需要判断是否有一个怪物可到达即可，这预示着我们可以对所有怪物一起处理。即多个源点的奇偶最短路。

处理完所有点的是能否走的情况后，我们开始构造方案。对于一个点 $i$ ，如果有多个同奇偶的 $t$ 可以经过这个 $i$ ，那么一定是 $t$ 最小的更优，因为在所有同奇偶的 $t$ 当中， $t$ 越大可以到达的点一定是更多的，这使得我们的行动愈发受限。

所以对 $1$ 的起点跑奇偶最短路，辅佐对能否被怪物干死的判断，即可得到一条 $1 \sim n$ 的路径。在奇数长路径和偶数长路径中选更短的那条即可。

最后是输出答案。本题的 std 书写错误，它是反着求最小字典序的（也就是 $1 \to 3 \to 2 \to 4$ 比 $1 \to 2 \to 3 \to 4$ 更优；而我的代码正确地处理了正着的最小字典序。因为 std 的错误处理，导致我 WA 了 $10$ 分的测试点。现在展现的是我正确处理了字典序的代码（实际 $90$ 分）：

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
ifstream cin("defect.in");
ofstream cout("defect.out");
 
const int kMaxN = 1e5 + 5;
 
int dis[kMaxN][2], len[kMaxN][2], a[kMaxN], f[kMaxN], n, m, d, k;
vector<int> e[kMaxN], p[kMaxN][2], g[kMaxN];
queue<pair<int, int>> q;
 
void bfs() {
  fill(dis[0], dis[0] + 2 * kMaxN, 1e9);
  for (int i = 1; i <= k; i++) {
    dis[a[i]][0] = 0;
    q.emplace(a[i], 0);
  }
  for (; q.size(); q.pop()) {
    auto t = q.front();
    for (int i : e[t.first]) {
      if (dis[t.first][t.second] + 1 < dis[i][t.second ^ 1]) {
        dis[i][t.second ^ 1] = dis[t.first][t.second] + 1;
        q.emplace(i, t.second ^ 1);
      }
    }
  }
}
 
// 在 t 时刻，x 是否会被干掉
bool check(int x, int t) {
  if (t % 2 == d % 2) {
    t = min(t, d);
  } else {
    t = min(t, d - 1);
  }
  return dis[x][t % 2] <= t;
}
 
void solve() {
  if (check(1, 0)) {
    cout << "-1\n";
    exit(0);
  }
  fill(len[0], len[0] + 2 * kMaxN, 1e9);
  for (q.emplace(1, 0), len[1][0] = 0; q.size(); q.pop()) {
    auto t = q.front();
    for (int i : e[t.first]) {
      if (!check(i, len[t.first][t.second] + 1)) {
        if (len[t.first][t.second] + 1 < len[i][t.second ^ 1]) {
          p[i][t.second ^ 1].clear();
          p[i][t.second ^ 1].push_back(t.first);
          len[i][t.second ^ 1] = len[t.first][t.second] + 1;
          q.emplace(i, t.second ^ 1);
        } else if (len[t.first][t.second] + 1 == len[i][t.second ^ 1]) {
          p[i][t.second ^ 1].push_back(t.first);
        }
      } 
    }
  }
}
 
void paint(int x, int b) {
  if (f[x]) {
    return;
  }
  f[x] = 1;
  for (int i : p[x][b]) {
    g[i].push_back(x);
    paint(i, b ^ 1);
  }
}
 
void print() {
  for (int x = 1; x != n; ) {
    cout << x << ' ';
    x = *min_element(g[x].begin(), g[x].end());
  }
  cout << n << '\n';
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> d;
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  cin >> k;
  for (int i = 1; i <= k; i++) {
    cin >> a[i];
  }
  bfs();
  solve();
  if (len[n][0] == 1e9 && len[n][1] == 1e9) {
    cout << "-1\n";
    return 0;
  }
  if (len[n][0] < len[n][1]) {
    cout << len[n][0] << '\n';
    paint(n, 0);
  } else {
    cout << len[n][1] << '\n';
    paint(n, 1);
  }
  print();
  return 0;
}

树上纯树

李超线段树树形dp

考虑最简单的动态规划：设 $d p_{i}$ 表示 $i$ 到其子树中的任意叶子节点需要的最小费用。那么对于已经是叶子节点的 $i$ ，有 $d p_{i} = 0$ ；否则枚举子树中的任意节点 $j$ $(j \neq = i)$ ，求 $min (a_{i} b_{j} + d p_{j})$ 。

时间复杂度 $O (n^{2})$ ，可以写一个启发式合并。然后……就不会优化了。需要用李超线段树解决子树的问题，然后线段树合并。但是我不会。

Haokee Note

Explorer

2025.10.14 模拟赛

好冷好热好冷好热

杀戮尖塔

故障机器人

树上纯树

Graph View

Table of Contents