山大校赛 2024 决赛 ABCDGHIJ 题解

因为太菜，暂时没有 L，且 EFK 还在更新，此三题预计在一周内更完。

  • 2024.12.17：感冒并在学校硬抗了六节课之后扛不住了，请假回家并更新了 G 题和各题的自评难度。

花絮

这位可爱的初四小朋友继赛前一周 NOIP 失利（本来就只有 然后挂了一个点到 结果全省 出头变成 ）后又在本次比赛中的 I 题发现了关键性质后瞪了一个点愣是没转化出来，喜提六题 rk7 遗憾离场。本人赛时成绩插入大一组是 rk2，大二以上组只有 rk11，校内（在很多高年级神犇都没来的前提下）只有 rk3，还是太菜了。

本题解按照我自认为的题目难度排序。

B

自评难度：红。

大纲（本人做法）：

  • 【1】初中代数（J）
  • 【3】整除（J）

每次循环先扣 点血量，再涨 点架势条，即血量共需要 回合打完，架势条共需要 回合打完，取最小值即可。复杂度 每组。

J

自评难度：下位蓝。

大纲（本人做法）：

  • 【8】分块（NOI）

赛时想抢一血然后看这题挺可爱的就开了于是喜提两发不管怎么说最后还是一血上了。

这种乍一看不怎么好上数据结构而数据范围又只有 级别的东西容易想到分块。于是每 （本人为了防止炸掉给它加了 ）个元素分一个块，每个块维护一个 tag 记录操作一，接着一旦出现操作二就把操作位置所在块的 tag 进行下传后暴力修改即可。注意两点：

  • 同一个块内连续（中间没有操作二）打 tag 时保留最大值，别直接覆盖了。
  • 跑完之后把所有块再下传一遍。

复杂度 。

C

自评难度：黄~下位绿。

大纲（本人做法）：

  • 【4】二分法（J）

求最值题，找单调性，发现有，于是直接二分答案，check 函数内模拟即可，注意当 为 时剩的全是小 的就不要再跑了。复杂度 ，其中 是一个可以接受的常数。

I

自评难度：上位绿~下位蓝。

大纲（本人做法）：

  • 【9】置换群与循环群（NOI）（估计只有这一个了？）

看到这个题很难不去想交换两个数之后置换环的变化。画出图来可知任意两元素交换，则原来同环变不同环，不同环变同环。但答案需要的是环的个数的奇偶性，所以进行转化，结论变为每次交换都会改变奇偶性（但是我赛时居然一个小时也没得到……），于是预处理出原排列中置换环的个数然后每次询问时算出操作了多少次再套刚才那个结论就做完了。预处理 ，单次询问 。

A

自评难度：中位绿~上位绿。

大纲（本人做法）：

  • 【1】枚举法（J）
  • 【5】桶排序（S）（非必要，可以优化复杂度和码量）

大纲没有拆贡献的相关思想，差评。

数据范围这么大直接算肯定是很难的，而且方案也不好构造。因此只能考虑拆贡献。

对于每个字符都可以让它和其余所有的同字符之间产生对称轴，因此子串的个数就是此时该字符的个数（包含自身，因为长度为 的也算）。每次暴力枚举或者开桶维护都可以，复杂度分别为 和 。

H

自评难度：中位蓝。

大纲（本人做法）：

  • 【4】简单一维动态规划（J）

暴力枚举三个字符是 的，无法接受。于是考虑优化。

首先可以后缀和维护一下每个字符后面有多少个 R/G/B/*，复杂度降至 。接着对着刚才求出的后缀和再来一遍后缀和计算每个字符后面 RB/R*/*B/BG/B*/*G/GR/G*/R*/** 的数量，这里式子项数略多所以建议是不要把 * 和 R/G/B 合并，单独计算的话比较清晰，且不容易算重。然后根据题意列式子统计答案即可。时间复杂度 ，常数比较大。

D

自评难度：上位绿~下位蓝。

大纲（本人做法）：

  • 【2】乘法原理（J）
  • 【4】动态规划的基本思路（J）（因为不是一维的，参考 CSP-J2023 第二轮分析报告的处理方式进行标记，报告中建议难度为 ）
  • 【8】动态规划的常用优化（S）

有点像 NOIP T2。

输赢的性质有点麻烦，先考虑不限制输赢怎么做。

看到数据范围想到 DP。对于我这种蒟蒻来说一个比较容易想到的暴力 DP 是设 为进行到第 回合，小 Z 的最小值为 ，小 W 的最小值为 的方案数。但是这样可以转移的情况很多（因为我们也不知道全局次小、第三小等等都在谁家里）导致复杂度达到了 。

列出转移方程后可以发现我们其实只需要 里较小的那个即全局最小值，因此状态改为 为第 回合全局最小值为 的方案数，转移类似于刚才，下一个 可能取 中的任意值。

接着考虑固定输赢的限制。首先大胆猜想没啥限制，因为似乎可以通过交换两边对应位置角色的方式来改变输赢。但是跑不过样例。于是找原因。打表之后发现是因为交换后小 W 将可能不会在那一回合使用那个角色因为它更大/更小了。因此考虑在限制下到底能往哪些方向转移。我们发现我们刚才猜想没啥限制的原因在连续的 Z 胜或 W 胜中仍然有效（因为此时根本不需要换），于是考虑 ZW 交替的地方。假设第 回合胜方由 Z 变为 W，则在某一回合要求 Z 拿最小值而下一回合换 W 拿最小值，分讨一下各种情况发现此时 W 应该只能拿 ，Z 拿 ，所以说交替处没有额外贡献，对每个连续段跑刚才的 DP 并乘起来即可。复杂度 。

G

自评难度：中位紫~上位紫。

大纲（本人教练做法）：

  • 【6】最小生成树：Kruskal 算法（S）
  • 【7】笛卡尔树（S）
  • 【6】树的重心、直径、DFS 序与欧拉序（S）
  • 【6】树上差分、子树和与倍增（S）
  • 【6】最近公共祖先（S）
  • 【6】线段树（S）
  • 【8】离线处理思想（NOI）

听说存在使用虚树的 做法但显然我是不可能会那种十级算法的。 有会的大佬欢迎补充。

重点前置在线段树和 Kruskal 重构树。

补这题给我补爽了。

首先介绍下 Kruskal 重构树的思想。（会的直接看下一段即可）

考虑这样一个问题：给定一张无向图，多次询问求两点间最小瓶颈。

  • 首先考虑暴力做法。我们进行优先队列 BFS，状态就是到达了哪个点以及到达这个点的瓶颈，每次找瓶颈最小的状态扩展。
  • 考虑优化。发现这个过程很像我们 Kruskal 算法的每次取最小边，进而发现两点间的最小瓶颈就是使它们第一次出现在同一个并查集内的那条边。
  • 发现合并两个并查集的过程就是合并两个区间，进而建出类似于线段树的树形结构，每个节点处记录一个点集和连接两个儿子点集的边的长度。这样这棵树的叶子就是每个节点，而我们要找的最小瓶颈就是这两个节点之间的 LCA。这棵树就叫做 Kruskal 重构树。

于是多次询问求最小瓶颈就是 Kruskal 重构树的经典应用。

于是我们发现：题目中的“瓶颈恰好为 的路径”和刚才那个玩意很像，于是把思路往 Kruskal 重构树上靠。于是根据 的值分为三类：

  • 小于 与 间的最小瓶颈，此时明显没有合法的路径，直接输出 ；
  • 等于 与 间的最小瓶颈，此时明显重构树上路径最优；
  • 大于 与 间的最小瓶颈：先判是否存在长度为 的边，如果存在的话，可以贪心地想到对于一条从 到 的长度为 的边， 到 经过它的最优路线为（如图）：
    • 到 走树上路径；
    • 到 走长为 的边；
    • 到 走树上路径。
    • 然后对着所有长度为 的边做一遍，你就会发现：

复杂度是错的。显然数据只要所有边全设成 然后对着 疯狂询问就趋势了。所以考虑优化。根据刚才的 hack 我们希望优化的方向就是将所有长度相同的边一块处理。

由于我们希望找到 到所有 及所有 到 的最小瓶颈，所以我们考虑将所有的长度为 的边都标记到重构树上，也就是我们希望在树上找一个深度不超过 的尽可能深的点，满足至少存在一个长度为 的边 使得 在以该点为根的子树中。

容易想到外层二分一下深度，此时需要快速的子树询问，想到 DFS 序，以 DFS 序为下标用线段树维护整棵重构树，对于每种瓶颈长度的询问，在处理之前将所有这种长度的边的 LCA 都标记为 ，这样求子树内是否完整包含一条长为 的边就转化为了线段树区间求和，因为一共就不超过 条边，所以最终的复杂度在 级别。