多校A层冲刺NOIP2024模拟赛15
T1 追逐游戏 (chase)
签到题
注意到三个点构成的树就是全部路径，找到交汇点（两两 lca 中 dep 最大的那个），分讨能否在终点前追上即可。
时间复杂度为 \(O(nlogn)\)
T2 统计
哈希，差分
维护每个值的前缀个数，发现合法段的两个前缀个数的形态一致，只是整体会多一些数，所有数减去最少的个数存即可。hash 不知道为什么不会冲突（？
时间复杂度为 \(O(Tnw)\)，其中 \(w\) 为哈希表的复杂度。
T3 软件工程
贪心，DP
注意到交集为空的集合至多有 \(1\) 个，证明考虑若有多个则可合并为一个，给其他腾位置。
考虑分讨是否有交集为空的集合
-
有，则答案为长度前 \(k-1\) 大之和
-
无，注意到若线段 \(i\) 能完全包含一个线段 \(j\)，则 \(i\) 要么单独成为 \(1\) 个线段，要么与 \(j\) 在同一个集合，证明考虑交集是一个贡献不增的过程。对于剩下的部分排序后左右端点都是单调的，则贪心选择连续一段最优，可以 DP 完成这一部分，前缀和优化后这一部分的时间复杂度为 \(O(nk)\)，其他线段类背包转移进去即可。
答案取两种情况最大值。
时间复杂度为 \(O(nk+nlogn)\)。
T4 命运的X
期望，构造，图上随机游走，高斯消元
-
对于前 60%
注意到每次选择的不是下一个则是一个跳 border 的过程，将移动变成边则成了一个有环有向图，直接随机游走高斯消元即可，时间复杂度为 \(O(n^3)\) (注意：由于只有出边的概率已知，所以得倒着求期望，即设 \(f_i\) 表示从 \(i\) 到 \(n\) 的期望步数) -
对于另外 20%
注意到每个点只有两条出边，可以直接代方程化简，记 \(s=\sum_{k=0}^{n-1}\dfrac{1}{m^k}\) 化简得 \(f_0=\dfrac{s}{1-\frac{m-1}{m}s}\)，时间复杂度为 \(O(n)\) -
对于 100%
人类智慧看不懂。