SSP Round - 09.08 赛后总结

zrl123456 · 2025-09-09 09:24:07 · 题解

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

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

A. 缥缈愿：

:::::info[题目基本信息] 考察：数学。
题目简介：
给定 \{a_n\} 和 k，求：

数据范围：

• 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 表，线段树，猫树，最小生成树，常数优化。
  题目简介：

  数据范围：
• 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