2025.11.25 模拟赛

Happy Card

首先看到如此恶心的 T1 大脑先未响应半小时再说。接着不难发现炸和 三带一 可以合并成额外带的牌没有任意限制的 三带一。

考虑贪心。显然尽量使用 三带一 是最优的，因为这种方法可以一次去掉 $4$ 张牌，就算影响到了剩余牌的奇偶性，也能视作丢掉 $3$ 张牌。

所以我们可以尝试求 $i = 1 \sum n ⌊ \frac{a _{i}}{3} ⌋$ ，即可以打出 三带一 的最多次数。但是打完后剩余的牌不能小于这个数，否则带不上单牌。所以考虑二分 三带一 的次数，在满足次数的情况下剩余牌数量不能小于 三带一 的次数。

bool check(LL x) {
  LL need = x, res = 0;
  for (LL i = 1; i <= n; i++) {
    LL add = a[i] / 3;
    if (add <= need) {
      need -= add;
      res += a[i] % 3;
    } else {
      res += a[i] - need * 3;
      need = 0;
    }
  }
  if (need || x > res) {
    return 0;
  }
  return 1;
}

现在我们得到了可以打出的 三带一 的最多次数，模拟一遍后得到打出 三带一 中的 三个同样的牌 的剩余牌。现在我们需要打出 三带一 对应的单牌。

另外两种出牌方式是单牌和对子。对于 $x$ 张剩余的牌，它需要最少 $⌊ \frac{x}{2} ⌋$ 的次数才能打完。所以我们打完 三带一 所对应的单牌后，奇数的数量要尽量少。

贪心地考虑，可以先把所有奇数的牌打掉。如果还剩奇数张牌要丢，那么就只能额外加一个奇数了。所以分类讨论打的单牌能否打掉所有的奇数牌即可。

最后我们先计算出 $i = 1 \sum n ⌊ \frac{a _{i}}{2} ⌋$ （如果最后打掉奇数的还剩下 $res$ 个需要打出，那么这个值可以减掉 $⌊ \frac{res}{2} ⌋$ ），而最后奇数的数量是可以计算出来的。加起来再加上最初 三带一 的数量即可得到答案。

Q & A

Q：既然我们是随便选的牌打三带一中的三张，那么有没有可能会导致剩余的牌当中奇数的数量达不到最优？

A：把 $- 3$ 从 $x$ 移到 $y$ ， $x$ 和 $y$ 的奇偶性会同时改变，所以剩下的奇数数量一定是一样的。

int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    LL sum = 0;
    for (LL i = 1; i <= n; i++) {
      cin >> a[i];
      sum += a[i];
    }
    LL tim = 0, need = 0;
    for (LL l = 0, r = sum; l <= r; ) {
      LL m = (l + r) / 2;
      if (check(m)) {
        tim = m;
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    for (LL i = 1; i <= n; i++) {
      LL add = a[i] / 3;
      if (need + add <= tim) {
        need += add;
        a[i] %= 3;
      } else {
        a[i] -= (tim - need) * 3;
        need = tim;
      }
    }
    LL cnt = 0, ans = 0;
    for (LL i = 1; i <= n; i++) {
      cnt += a[i] % 2;
      ans += a[i] / 2;
    }
    if (tim < cnt) {
      cout << tim + (cnt - tim) + ans << '\n';  // 减掉部分奇数的
    } else {
      cout << tim + ans - (tim - cnt) / 2 << '\n';  // 减掉所有奇数的，再减掉额外的（两次可以减小一次答案）
    }
  }
  return 0;
}

Speaker

树形dp 树链剖分线段树 ST表最近公共祖先前缀和倍增

首先我们把 $x \to z \to y$ 的路线看成在 $x \to y$ 的路径上取一个点 $p$ ，使得 $x \to p$ 然后从 $p$ 往返到 $z$ 、最后从 $p \to y$ 的路线最近。

为什么一定是这样呢？不能从 $p$ 直接走到 $y$ 而不回到 $x \to y$ 路径上吗？当然不行，这样子两点间就会有超过一种走法，不符合树的结构。

于是问题就转化成了在 $x \to y$ 的路径上取一点 $p$ ，使得另外任意一点 $z$ 有 $a_{x} + 2 \times d_{(p, x)}$ 最大。答案最后再加上 $d_{(x, y)}$ ，因为这是一定要走的部分。

整个路径上每个点的信息并很好维护，但是我们需要求出对于每个点 $i$ 的值 $j = i max n (a_{j} + 2 \times d_{(i, j)})$ 才可以维护。

这个值可以通过树形 DP 和换根解决。首先先考虑 $j$ 在 $i$ 子树中的情况，那么对于 $f_{i}$ （初始化为 $a_{i}$ ），枚举 $i$ 的儿子 $j$ ，令 $f_{i} \leftarrow max (f_{i}, f_{j} + 2 \times w_{(i, j)})$ 。

void dfs1(LL x, LL f) {
  down[x] = a[x];
  for (auto i : e[x]) {
    if (i.first == f) {
      continue;
    }
    pre[i.first] = pre[x] + i.second;
    dfs1(i.first, x);
    down[x] = max(down[x], down[i.first] - 2 * i.second);
  }
}

然后考虑 $j$ 不在 $i$ 子树中的情况（为了方便规定 $j = i$ 合法），设最大值为 $g_{i}$ 。那么对于 $i$ ， $j$ 可以：

存在于它的兄弟的子树当中。遍历父亲时，对儿子的 $f$ 值做前缀后缀最大值就可以对儿子转移时查询。
不存在于它的父亲的子树当中，即要向上至少两层。那么可以通过父亲的 $f$ 值转移过来。

这两个 DP 时间复杂度都是 $O (n)$ 的。

void dfs2(LL x, LL f) {
  up[x] = max(up[x], a[x]);
  vector<LL> son, val, pre, suf;
  for (auto i : e[x]) {
    if (i.first == f) {
      continue;
    }
    son.push_back(i.first);
    val.push_back(i.second);
    pre.push_back(down[i.first] - 2 * i.second);
    suf.push_back(down[i.first] - 2 * i.second);
  }
  for (LL i = 1; i < pre.size(); i++) {
    pre[i] = max(pre[i], pre[i - 1]);
  }
  for (LL i = (LL)suf.size() - 2; i >= 0; i--) {
    suf[i] = max(suf[i], suf[i + 1]);
  }
  for (LL i = 0; i < son.size(); i++) {
    up[son[i]] = max(i > 0 ? pre[i - 1] : (LL)-1e18,
                     i < son.size() - 1 ? suf[i + 1] : (LL)-1e18) -
                 2 * val[i];
    up[son[i]] = max(up[son[i]], up[x] - 2 * val[i]);
    dfs2(son[i], x);
  }
}

对于 $i$ ， $max (f_{i}, g_{i})$ 就是答案。

现在我们需要维护路径上的答案。首先可以想到重链剖分。由于不带修，用 ST 表维护 dfs 序所对应的序列的区间 $max$ 。单次查询时间复杂度 $O (lo g_{2} n)$ 。当然如果你大脑残废写了线段树把查询复杂度干到了 $O (lo g^{2} n)$ 好像也可以过。

不过倍增也是可以的，额外维护每个节点向上跳 $2^{k}$ 步经过的点的最大值也是可以的。时间复杂度 $O (lo g_{2} n)$ 。

维护 $1$ 到每个节点的路径长度，顺带求 LCA 来查询 $x \to y$ 的路程。

总时间复杂度 $O (n + q lo g_{2} n)$ 。

void prework1(LL x, LL f) {
  fa[x] = f;
  dep[x] = dep[f] + 1;
  siz[x] = 1;
  for (auto i : e[x]) {
    if (i.first == f) {
      continue;
    }
    prework1(i.first, x);
    siz[x] += siz[i.first];
    if (siz[i.first] > siz[son[x]]) {
      son[x] = i.first;
    }
  }
}
 
void prework2(LL x, LL t) {
  top[x] = t;
  dfn[x] = ++cnt;
  if (!son[x]) {
    return;
  }
  prework2(son[x], t);
  for (auto i : e[x]) {
    if (i.first == fa[x] || i.first == son[x]) {
      continue;
    }
    prework2(i.first, i.first);
  }
}
 
LL query(LL l, LL r) {
  LL k = lg[r - l + 1];
  return max(dp[l][k], dp[r - (1 << k ) + 1][k]);
}
 
LL solve(LL x, LL y) {
  LL res = 0, len = pre[x] + pre[y];
  for (; top[x] != top[y]; x = fa[top[x]]) {
    if (dep[top[x]] < dep[top[y]]) {
      swap(x, y);
    }
    res = max(res, query(dfn[top[x]], dfn[x]));
  }
  if (dep[x] > dep[y]) {
    swap(x, y);
  }
  res = max(res, query(dfn[x], dfn[y]));
  return res - (len - 2 * pre[x]);
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
  }
  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);
  }
  dfs1(1, 0);
  dfs2(1, 0);
  prework1(1, 0);
  prework2(1, 1);
  for (LL i = 1; i <= n; i++) {
    dp[dfn[i]][0] = max(down[i], up[i]);
  }
  for (LL j = 1; j < kLog; j++) {
    for (LL i = 1; i + (1 << j) - 1 <= n; i++) {
      dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (LL i = 2; i <= n; i++) {
    lg[i] = lg[i / 2] + 1;
  }
  for (LL x, y; q; q--) {
    cin >> x >> y;
    cout << a[x] + a[y] + solve(x, y) << '\n';
  }
  return 0;
}

Monotonic Queue

序列dp 单调栈

不会，写的爆搜，甚至答案计算都是抄的题面上的。成功获得 $4$ 分。

XA-Game

矩阵快速幂

不会，暴力都没打，成功 $0$ 分。

Haokee Note

Explorer

2025.11.25 模拟赛

Happy Card

Speaker

Monotonic Queue

XA-Game

Graph View

Table of Contents