北京大学 周佳仪 2026/10/7
糖珠甜甜圈
题意简述
- 给长为$n$ 的环染色,共$c$ 种颜色。任意连续$k$ 个位置中,颜色$j$ 恰好出现$b_j$ 次。
- 另有$q$ 条指定颜色的约束$a_{x_i} = y_i$;求合法序列数,模$P = 10^9 + 7$。按位置区分方案,不对旋转等价类计数。 *$T \le 10^4, 1 \le k \le n \le 10^7, c, q \le 10^5, b_j \ge 0, \sum_j b_j = k$。
- 全部数据的$\sum c, \sum q \le 10^5$,但没有$\sum n$ 的限制。
部分分
- 30 分:$n \le 10, c \le 2, T \le 10$。枚举染色,检查指定位置与各窗口的颜色计数,时间$O(c^n(n+c+q))$。
- 20 分:$k=n$。只限制整环的颜色总数;扣除指定位置后,用多项式系数计数。预处理后每组$O(c+q)$。
- 20 分:$q=0$。由相邻窗口得到长度$\gcd(n,k)$ 的周期,再对周期内的颜色数量计数,每组$O(c+\log n)$。
- 30 分: 无限制。将指定位置也映射到周期内,统一处理。
题解
- 相邻窗口只删除$a_i$、加入$a_{i+k}$;颜色计数不变,故$a_i = a_{i+k}$。
- 在模$n$ 意义下反复加$k$,恰好遍历一个模$d = \gcd(n, k)$ 的剩余类,因此整个序列由长为$d$ 的块重复而成。
- 每个长为$k$ 的窗口包含$t = k/d$ 份周期内的颜色计数,所以必须有$t \mid b_j$,周期内颜色$j$ 的配额为$h_j = b_j/t$。
- 反过来,满足这份配额的周期重复后,每个窗口都合法。问题等价于对$d$ 个位置按配额染色。
- 指定位置映射到它所属的模$d$ 剩余类;同一类若被指定不同颜色,则无解。
- 每个已固定的剩余类只消耗一个颜色配额;若配额不足,同样无解。
- 设还剩$r$ 个未固定位置,各色剩余配额为$h'_j$,则 $$ \mathrm{ans} = \frac{r!}{\prod_j h'_j!} \pmod{P}. $$
- 统一预处理阶乘与逆阶乘后,每组只需处理颜色与约束,时间$O(c + q + \log n)$;无需扫描整个环。
- 令$B = 10^7$,总时间$O(B + \log P + \sum (c + q + \log n))$,空间$O(B + c + q)$。
面包碎碎念
题意简述
- 长度$n$ 的面包进入机器 1;机器$i$ 将收到的面包尽量均匀地切成$k_i \in \{2,3,4\}$ 份,长的一份排在前面。
- 第$j$ 份送往机器$s_{i,j}$;长度 0 忽略,长度 1 直接结束。机器之间允许有环。
- 统计每种长度的面包出现次数,初始、途中和最终面包都计数,结果不取模。 *$1 \le n \le 2^{50}, 1 \le m \le 100$;每次切分后的正长度均严格变小。
部分分
- 15 分:$n \le 1000$;20 分:$n \le 10^6, m \le 5$。直接展开加工树;它有$n$ 个单位叶子,每个内部结点至少有两个儿子,总规模$O(n)$,时间$O(n+m)$。
- 25 分:$m=1$。切分份数$k$ 固定,每层只有$\lfloor n/k^h \rfloor, \lceil n/k^h \rceil$ 两种长度,合并计数可得$O(\log n)$ 时间。
- 20 分:$k_i \in \{2, 4\}$。累计除数只有$2^a$,长度数为$O(\log n)$;合并状态后时间$O(m \log n + \log n \log \log n)$。
- 20 分: 无限制。将累计除数推广到$2^a 3^b$。
题解
- 长度相同、所在机器相同的面包,后续加工过程完全一致,可以合并成一个带数量的状态。
- 沿一条加工路径,设切分份数的乘积为$D$,当前长度一定属于 $$ \{\lfloor n/D \rfloor, \lceil n/D \rceil\}. $$
- 原因是:再除以$k$ 后,最小可能值为$\lfloor n/(Dk) \rfloor$,最大可能值为$\lceil n/(Dk) \rceil$,两者至多相差 1。
- 这个结论允许每层任意选择较长或较短的一份。
- 由于$k_i \in \{2, 3, 4\}$,累计除数总能写成$D = 2^a 3^b$。
- 还能继续切分的面包长度至少为 2,因而$D < n$;再切分一次,累计除数也小于$4n$。
- 所以$a, b$ 都只有$O(\log n)$ 种可能;每个$(a, b)$ 只对应至多两种长度。
- 记不同正长度数为$L$,则$L = O(\log^2 n)$,而“长度、机器”状态数只有$O(mL)$。
- 以$(x, i)$ 表示长为$x$、到达机器$i$ 的面包;每个状态记录到达它的面包总数。
- 切分后长度严格减小,因此按长度递减计算,所有来源的数量都已确定;机器间有环不影响这一顺序。
- 将当前数量加入对应长度的答案,并沿每个非空出口传递;多个出口通向同一状态时,数量自然累加。
- 整理长度集合需$O(L \log L)$,每个状态只有常数条转移,总时间$O(L \log L + mL)$,空间$O(mL)$。其中$L = O(\log^2 n)$。合并的是计算过程,每块面包的出现次数仍然保留。
果酱分分乐
题意简述
- 维护非负数组$a$ 与排列$p$;
SWAP u v交换$p_u, p_v$。 MOD l r x对区间内所有位置同时赋值,右侧使用操作前的数组$\tilde{a}$: $$ a_i \leftarrow \tilde{a}_i \bmod \max(\tilde{a}_{p_i} + x, 1). $$- 每轮输出$\sum_i (a_i - a_i \bmod \max(a_{p_i}, 1))$;这次预测不修改数组。 *$n, q \le 10^5, 0 \le a_i, x \le 10^9$,允许$p_i = i$。
部分分
- 10 分:$n, q \le 500$。每轮按旧数组模拟,再重新求和,时间$O(nq)$。
- 15 分: 没有 MOD。交换标签只改变两处答案贡献,维护总和即可,总时间$O(n+q)$。
- 15 分: 所有 MOD 都满足$l=r$。每个瓶子恰好被一个瓶子参考,改变一个值只影响它自身与参考它的位置。因此单点取模与标签交换都只需处理常数处贡献,总时间$O(n+q)$,空间$O(n)$。
- 20 分:所有 MOD 都有$x=0$。用有序集合维护$a_i > 0$ 且$a_i \ge a_{p_i}$ 的位置,区间操作只枚举这些位置。每次有效取模都会减半。设总变化次数为$K$,则上述方法为$O((n+q+K) \log n)$。
- 15 分:没有 SWAP。参考关系固定,用后面的线段树方法处理不同阈值$x$。
- 25 分:无限制。交换参考关系仍只影响两处贡献与判定条件,可以一并维护。这里$K = O(n \log(A+1))$,(A$ 为初始果酱量的最大值。
题解
- 若正整数$a$ 对$b$ 取模后变小,则$b \le a$。当$b \le a/2$ 时,余数小于$b$;否则余数为$a-b$。两种情况都小于$a/2$。
- 因而全部操作中,数值变化总次数只有$K = O(n \log(A+1))$;关键是跳过不变化的位置。
- 对$a_i > 0$,本轮会变化当且仅当 $$ a_i \ge \max(a_{p_i} + x, 1) \iff a_i - a_{p_i} \ge x. $$
- 用线段树维护差值的区间最大值,就能跳过整段不满足阈值的位置;零值始终排除。
- 答案是各位置贡献$v_i = a_i - a_i \bmod \max(a_{p_i}, 1)$ 的总和。
- 因为$p$ 是排列,每个$a_i$ 只被唯一一个位置引用;改变它,只影响自身与参考它的位置。
- 所以本轮若有$s$ 个值变化,至多影响$2s$ 处贡献和差值;交换标签则只影响交换的两个位置。
- 同一轮必须以旧状态确定全部变化,再统一更新,才能保持“同时分装”的语义。
- 一轮 MOD 若有$s$ 个位置变化,线段树定位与局部维护共需$O((s + 1) \log n)$。
- SWAP 只涉及常数个位置,时间$O(\log n)$。
- 将所有轮次相加,再代入总变化次数$K$,得到 $$ O(n + (q + K) \log n) = O(n + (q + n \log(A + 1)) \log n). $$
- 空间$O(n)$。这个界约束整个操作序列,一次操作仍可能改变很多位置。
饼干连连看
题意简述
- 在有$n$ 个叶子的有根满二叉树中,选择至少两个叶子组成集合$V$。 *$L_Z(V)$ 是连接$V$ 的最小子树边权和;(L_S(V)$ 是以$V$ 为顶点、树上距离为边权的完全图的最小生成树权值。
- 求$\min_{|V| \ge 2} L_Z(V)/L_S(V)$,四舍五入保留三位小数。 *$2 \le n \le 1000$,共有$2n-1$ 个结点,边权为正整数且不超过$10^6$。
部分分
- 24 分:$n \le 8$;12 分:$n \le 16$。枚举叶子子集,分别求最小子树边权和、叶间距离图的 MST,总时间$O(2^n \text{poly}(n))$。
- 20 分:$n \le 100$。使用后面的分数规划与“最近叶子”树形 DP,跨边时直接枚举新旧最近叶子。每次判定$O(n^3)$,二分到精度$\varepsilon$ 的总时间为$O(n^3 \log(1/\varepsilon))$,空间$O(n^2)$。
- 12 分:边权全为 1。仍可用最近叶子 DP;跨边的候选距离落在宽度为 2 的窗口内,可按距离分组取最大值。
- 20 分:非叶结点构成一条链。沿内部结点链合并子树,仍维护最近叶子及跨边候选的距离范围。
- 这两档都可以共用后面的单调队列优化,把一次判定降为$O(n^2)$。
- 12 分:无限制。同一套优化适用于任意满二叉树;预处理后总时间$O(n^2 \log(1/\varepsilon))$,空间$O(n^2)$。
引理
- 记$T[V]$ 为连接$V$ 的最小子树,总边权为$W$,显然$L_Z = W$。
- 记$B(V)$ 为$T[V]$ 中的三度结点:每个结点到最近选中叶子的距离为$\delta_V(x)$。定义 $$ \delta_V(x) = \min_{v \in V} d(x, v), \quad D = \sum_{x \in B(V)} \delta_V(x). $$
- 关键结论是$L_S = W + D$:最小生成树比最小子树多出的费用,恰好来自这些三度结点。
