本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-09 09:24:07

:::::info[闲话] KSCD_ 大神/bx/bx

270pts，感觉打得还不错。
赛后补了 T1,T3。
:::::

A. 缥缈愿：

:::::info[题目基本信息] 考察：数学。
题目简介：
给定 $\{a_n\}$ 和 $k$，求：
$$\max_{l=1}^n\max_{r=l-1}^n\gcd(\gcd_{i=1}^la_i,\gcd_{i=l}^r(a_i+k),\gcd_{i=r+1}^na_i)$$ 数据范围：

• $1\le n\le 6\times 10^5$
• $1\le k\le 10^{18}$
• $\forall i\in[1,n],1\le a_i\le 10^{18}$ ::::: :::::info[考场做法] 乱搞。如果当前前面部分的 $\gcd$ 在 $[1,10^{17}]$ 范围内就进行枚举质因子判断可行性贪心，否则就暴力排除以最前面还未枚举的数开始的区间为被操作区间，记录进答案。 时间复杂度是玄学，拿了 95pts，由于剩余的 5pts 性价比太低就没有继续写。
  ::::: :::::success[正解] 由于前缀后缀 $\gcd$ 只有 $\log V$ 种取值，所以不妨枚举取值对于不同取值贪心 $\Theta(n+\log V)$ 求最大的 $\gcd$，记进答案。
  时间复杂度 $\Theta(n\log^2V+\log^3V)$，空间复杂度为 $\Theta(n)$。
  :::::

B.虚构义：

:::::info[题目基本信息] 考察：ST 表，线段树，猫树，最小生成树，常数优化。
题目简介： $h$ 个点 $n$ 条边的无向带权图，$q$ 次询问，求编号为 $[l,r]$ 的边的最小生成树。
数据范围：

• $1\le n,q\le 5\times 10^5$
• $1\le h\le\color{red}10$ ::::: :::::success[赛时做法（正解）] 注意到只有 $\displaystyle\frac{h(h-1)}{2}=45$ 种端点不同的边，同时端点不同的边显然取边权最小的，所以我们可以用 ST 表维护（由于空间和时间卡，所以我们要用指针动态开 ST 表，既节省空间常数，也节省时间常数），然后每次询问直接 Kruskal/Prim 做即可。
  时间复杂度为 $\Theta(n\log n+qh^2\log h)$，空间复杂度为 $\Theta(n\log n+h^2)$。
  :::::

C. 短恨歌：

:::::info[题目基本信息] 考察：组合数学。
题目简介：
一棵 $n$ 个点的树上有 $k$ 个黑点，求有多少种可能使得到所有黑点的距离和最小的点唯一（对 $998244353$ 取模）。
数据范围：

• $1\le k\le n\le 10^6$ ::::: :::::info[赛时做法] 暴力加性质，45pts。
  ::::: :::::success[正解] 注意到 $k$ 为奇数时任意放黑点均合法，直接输出 $\displaystyle\binom{n}{k}$。
  否则，直接正难则反，注意到这些点构成一条路径，不妨继续正难则反，求出所有存在大于 $1$ 的路径的最近公共祖先的方案数，然后用所有是符合条件的点方案数的总点数减它，再用总方案数减它即可，代码并不难写。
  时间空间均线性。
  :::::

T4 最后还有 30pts，是一个单侧递归线段树，并不想写，也不会。

KSCD_ 大神/bx/bx