2025 多校冲刺省选模拟赛 1

切割蛋糕（cake）

签到题

本质上是求 \(a\) 序列最小满足所有前缀平均值均大于全局平均值的循环位移，由 Raney 引理启发，找到斜率 \(\dfrac{s}{n}\) 所经过截距最小的点，易知没有无解情况。

时间复杂度 \(O(n)\)。

游乐园（park）

可反悔贪心

考虑答案小于等于 \(k\) 时，优先选取 \(b\) 排序后的前 \(ans\) 个。

若答案大于 \(k\) 时，则考虑通过调整得到答案。

具体的考虑是加入一个 \(a\) ，或是替换一个 \(b\) ，选取代价小的优。

证明：考虑当前局面是由上一个最优局面转移而来，而上一个最优局面无论怎么调整都不会使得代价更小，而当前局面选择的是代价最小的，依旧满足不存在一种调整方案使得代价更小。

实现上可以维护 \(3\) 个优先队列，分别维护 \(a,b,a-b\) 的值。

时间复杂度 \(O(n\log n)\).

有根树（tree）

题意转化，组合数学，数据结构

考虑实链带来的限制是什么，记一条实链中深度最大的点为 \(id\)，那么在序列中所有实链上的点 \(u\) 都应满足限制 \(p_u<p_{id}\)，并且 \(id\) 的所有儿子 \(son_{id}\) 也应满足限制 \(p_{son_{id}}<p_{id}\)，总共有 \(n-1\) 个限制，且每个至多会在小于限制一方一次，则这些限制构成了一颗重构树。

重构树中的点满足所有儿子在序列中的位置在自己之前，儿子之间的位置互不干扰。

考虑在这颗重构树上计数（以下定义均考虑在重构树上），记 \(f_i\) 表示只考虑 \(i\) 子树内（包括自己）的点序列的方案。考虑转移，转移实际上就是合并两个限制独立的序列，考虑插板合并，记 \(s_{i,j}\) 表示 \(i\) 前 \(j\) 个子树的大小之和，则 \(f_i=\prod_{v_j\in son_o} f_{v_j}\dbinom{s_{i,j}}{sz_{v_j}}\) ，由于是乘积的形式则答案等于 \(\prod_i\prod_{v_j\in son_i}\dbinom{s_{i,j}}{sz_{v_j}}\)，注意到后面一个部分实际上是一个多项式系数合并后变为 \(\prod_i\dbinom{sz_i-1}{sz_{v_j},sz_{v_{j+1}\dots}}\) 直接拆开合并得到 \(\dfrac{n!}{\prod_vsz_v}\)。

考虑重构树上 \(sz\) 和原树的关系 ，记 \(top_{id}\) 表示以 \(id\) 这个点作为实链最下端点的链最上方的点，则重构树上的 \(sz_{id}\) 等于原树上的 \(sz_{top_{id}}\)。

考虑怎么快速修改，注意到修改操作是一个颜色推平的形式，且满足颜色段均摊，暴力树剖加线段树 or 珂朵莉得到 \(O(n\log^2 n)\) 做法，略卡常。考虑优化，注意到每次对一条重链推平只会更改链顶部分，用一个栈即可维护，得到 \(O(n\log n)\) 的做法。

集合操作（set）

概率期望，拆贡献

直接统计毫无人能做，考虑期望的线性性，即统计每个点对答案产生的贡献，考虑将删除操作视为一个全排列，一个数会被删除当且仅当这个排列中所有它的约数都在它的后方，显然 \(E(i)=\dfrac{1}{d(i)}\)，则答案等于 \(\sum_{i\le n}\dfrac{1}{d(i)}\)，由于 \(n\) 比较大，考虑使用 min25/洲阁筛。