南方科技大学 2025 新生赛简要题解

BY 来自深海\_FromOceans (QQ:2405097478)

因为官方没有发题解，所以自行为这场比赛的题目写了题解。

民间题解不代表官方做法，仅为在OJ上通过的做法。

A

给出 $n,m,k,q,x$ 和序列 $\{a_n\}$，可以进行 $q$ 次 $a_i\gets min(m,a_i+x)$，最大化序列的第 $k$ 大数。

Difficulty: 1 , Quality: C

显然只有前 $k$ 大的数字有用，对于其他数字我们摆烂不加它们一定更优。问题变成最大化最小数。

直接二分答案 $ans$ 并试图检查让所有数字大于 $ans$ 的可行性，接下来即检查能否在 $q$ 次内把所有数加到 $ans$，一个数需要被加的次数就是 $\lfloor\frac {ans - ai} {x}\rfloor$。

时间复杂度 $O(n\log A)$。

Code

B

给出 2D-plane里 $n$ 个点，统计 无序四元组 $(i,j,k,l)$ 满足 $i$ 在 $\triangle jkl$ 中 的个数。

Difficulty:6 , Quality: A

因为点 $i$ 较为特殊，故枚举 $i$，然后剩下三个点组成的三角形包含它的充要条件是 “以这个点为极坐标的原点，剩下三个点不在同一个半平面内”。 故确定该点后将其它点按极角排序，用双指针统计三个点在同一个半平面的方案数即可。

注意三点共线的的情况可能会算重，精细实现即可。

Code

反思：

最开始做的时候一直试图枚举两条边或是枚举三个点再统计。但事实上“形成三角形并包含某点”的条件是很弱的，因此可以在确认了特殊的那个点之后简单地统计。

C

求 $1-n$ 中每个数的最大平方因子的和。

Difficulty:4.5 , Quality: B+

比较考验筛子思想的一个题目。

先考虑枚举一个最大平方因子 $x^2$ ，然后剩余的质因子数量都等于 $1$，于是我们就要求出 $kx^2 \leq n$ 的 $k$ 的个数，满足 $k$ 是若干不同质数的乘积，令 $f(n)$ 表示 $1\sim n$ 中所有质因子的指数都是 $1$ 的数的数量，我们就是求 $\sum_{x^2}f(\lfloor\frac n{x^2}\rfloor)\times x^2$。

考虑如何求 $f(n)$，求所有因子都是 $1$ 比较困难，我们单步容斥，减去那些存在一些数的指数大于等于 $2$ 的情况，即存在一个大于 $1$ 的平方因子。

于是我们枚举一个 $x^2$ 作为这个数最大的平方因子。那么接下来再选取一个数满足所有数的指数都不超过 $1$ 的数 $m$，乘起来所有 $mx^2\leq n$ ，这样就枚举了最大平方因子恰好为 $x^2$ 的数， 也就是说，对于 $x^2$，这样的数 $m$ 有 $f(\lfloor\frac n{x^2}\rfloor)$ 个。

于是我们可以递推 $f(n) =n - \sum_{x^2 ,x>1} f(\lfloor\frac n{x^2}\rfloor)$。

因为 $\lfloor\frac{\lfloor\frac{n}x\rfloor}y\rfloor =\lfloor\frac{n}{xy}\rfloor$ ，所以我们能访问到的 $f()$ 仅会是 $f(\lfloor\frac{n}{x^2}\rfloor)$ 的形式，通过递归、记忆化的方式是求出 $f(n)$，显然时间复杂度不高于 $O(n^{0.75})$，理论可过。

实现时直接线性处理一下 $O(n^{2/3})$ 级别的 $f$ 值，将复杂度压缩至 $O(n^{2/3})$。复杂度分析同杜教筛。

Code

D

你有 $m$ 个初始值为 $0$ 的 $a_1\dots a_m$，你需要进行 $x$ 次 $a_i\gets a_i +2$ 和 $y$ 次 $a_i \gets a_i + 3$，最小化 $\max{a_i}$。

$m,x,y\leq 10^6$.

Difficulty: 4 , Quality: B

感谢 周昊天 提供的优雅做法，非常精妙。

考虑 $+2$ 和 $+3$ 只差了 $1$，于是我们试图先达到一种较优秀的情况再进行微调。

于是有这样一种很神秘的分类做法：

若 $+2$ 次数多余 $+3$，则不妨假设全部都是 $+2$，然后额外将 $y$ 个 $+2$ 替换为 $+3$，于是接下来 $y$ 次直接选择最矮的 $+1$ 即可，次数一定够。

若 $+2$ 次数不多于 $+3$，则不妨假设全部都是 $+3$，然后额外将 $x$ 个 $+3$ 替换为 $+2$，于是接下来 $x$ 次直接选择最高的 $-1$ 即可，次数一定够。

于是我们简单优雅地使用堆模拟即可通过此题，复杂度 $O(n\log n)$，优化一下可以更快。

这个题我使用很复杂、很邪恶的讨论过掉的，甚至可以做到 $O(1)$，正确性通过对拍验证，放在后面。

Code

E

给出一个字符串 $S$，在 $base = 2333333,mod = 998244353$ 下进行字符串哈希，找到其所有子串的哈希值的最大值。

$T\leq 50,\sum|S|\leq 2\times 10^6$

Difficulty: 6.5 , Quality: A+

很需要想象力的题目。

首先我们有做法：$O(n^2)$ 地枚举每个串并统计哈希值。

思考如何利用随机这个性质。

因为字符串和哈希值都是比较随机的，我们可以近似认为 $O(n^2)$ 个哈希值均匀分布在 $[0,mod)$ 中，这意味当 $n$ 很大的时候，最大的那个哈希值离 $mod$ 不会太远。

首先需要知道 $[0,N]$ 中 $K$ 个随机数的最小值的期望是 $N/(K+1)$，于是我们可以观察到，最大值离 $mod$ 的期望距离是 $O(\frac {mod}{n^2})$ 的，这意味着随着 $n$ 变大，子串个数以平方的速率变大，而最大值离 $mod$ 的期望距离快速减小。

于是我们在 $n$ 较大时，直接从 $mod - 1$ 开始倒序枚举每个哈希值，并检查其是否存在。

检查一个哈希值是否存在于一个字符串中显然可以扫一遍，通过 umap 存下之前所有哈希值乘上对应系数来找到。

单次时间复杂度 $O(n)$，期望进行 $O(\max(1,\frac {mod}{n^2}))$ 次，单组时间复杂度 $O(n+\frac {mod}{n})$.

于是我们进行数据分治,构造阈值 $B$。对于 $n\leq B$ ，进行 $O(n^2)$ 的算法；对于 $n>B$，进行 $O(\frac {mod}{n})$ 的算法。

最优阈值满足两侧时间复杂度最大值相同，所以 ${B^2}=\frac {mod}{B}$，$B=O(mod^{1/3})$。

所以时间复杂度可以达到 $O(mod^{2/3}+n)$。

因为题目多测并保证 $\sum n$,所以我们在 $B=3000$ 附近达到复杂度的上界是 $O(T\times (\frac{mod}B+B^2))$,略微卡常，需要手写哈希表。

剩下题目稍后补全。