SSP Round 题解

KSCD_ · 2025-09-07 21:33:56 · 题解

前言

T1 数据造水了。谢罪。

T3 数据造水且造错了，最后修了三次才对。谢罪谢罪谢罪。

题目难度可能偏高，这是赛前没有预料到的，比较抱歉。

U606783 缥缈愿

出处：SDSC2025 D1T1 By yixiuge777.

该题在原赛时作为 T1 通过率为 \frac {15}{48}。

Sol.5,6 是两种不同的 std。

题意

给出长为 n 的序列 a_i，可进行一次区间加 k 操作，求全局 GCD 的最大值。多测，T\le 3,n\le6\times10^5,a_i,k\le 10^{18}。

Sol.1

暴力枚举 [l,r] 后暴力计算 GCD。时间复杂度 O(n^3\log V)，期望得分 10。

Sol.2

预处理前后缀 GCD，然后先枚举 l，在枚举 r 的过程中维护中间部分 a_i+k 的 GCD。时间复杂度 O(n^2\log V)，期望得分 30。

Sol.3

答案较小时可枚举答案 res，若存在 res\nmid a_i 且 res\nmid a_i+k，则该答案一定不合法。之后每个 a_i 可能必须加 k，可能必须不加，也可能两者皆可。找到必须加的第一个和最后一个位置 [l,r]，当且仅当该区间内部都能加时答案合法。时间复杂度 O(nV_r)，其中 V_r 为答案值域。期望得分 20。

Sol.4

当 a_1=1 时，若 l>1 则 GCD 必为 1，因此 l=1。类似 Sol.2 中的方式枚举 r 即可，a_n=1 的情况是类似的。时间复杂度 O(n\log V)，加上 Sol.2 期望得分 40，拼上 Sol.3 期望得分 60。

Sol.5,6

观察一下答案结构，是前后缀各一段再拼上中间加 k 的形式。又由于前缀 GCD 只有 O(\log V) 段不同取值，猜想每段有用的 l 很少。事实的确如此，若结尾在 [L,R] 内的前缀 GCD 均为 g，则 l=R+1 在 l\in [L+1,R+1] 中一定最优。证明考虑最终答案是 g_L,g_M,g_R 三者的 GCD，而这段 l 对应的 g_L 均为 g，此时把尽可能少的数划到中间一定更优。同理也只有 O(\log V) 个有用的 r。

Sol.5

可以直接类似 Sol.2 枚举所有有用的 l，同时只在有用的 r 处统计答案。这里由于 GCD 不变时函数只会运行 O(1) 次，直接维护中间部分 GCD 就是 O(n+\log V) 的。由于统计答案时还要算一次 GCD，总复杂度为 O(n\log V+\log ^3V)，期望得分 100。

Sol.6

直接暴力枚举所有合法对 [l,r]，g_L 和 g_R 容易前后缀预处理。考虑使用 ST 表维护区间 GCD，复杂度 O(n\log^2V+\log^3 V)，期望得分 65，拼上 Sol.4 期望得分 75。但 chb 说这个是均摊 O(n\log V) 的，不懂，反正过不了。

事实上注意到关键点只有 O(\log V) 个，考虑只对这些点建 ST 表，即 w_i 表示两个关键点之间的 GCD。预处理 w_i 只需 O(n\log V) 的复杂度，对 w 建出 ST 表后枚举区间即可，总复杂度 O(n\log V+\log^3V)，期望得分 100。

U606784 虚构义

出处：SDSC2025 D4T2 By Mikefeng.

该题在原赛时作为 T2 通过率为 \frac 7{48}。

Sol.6,7,8 是三种不同的 std，均使用 Prim 求解最小生成树，事实上也并没有卡 O(qh^2\log h) 的 Kruskal。

Sol.9 是 chb 提出的做法，作为补充 std。

题意