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

A. k-th divisor：

:::::info[题目基本信息] 考察：数学，数论（$1400$）。
题目简介：
给定 $n,k$，求 $n$ 的第 $k$ 大因子，若不存在输出 -1。
数据范围：

• $1\le n\le 10^{15}$
• $1\le k\le 10^9$ ::::: 注意到 $n$ 的因数 $p$ 一定满足以下条件之一：

1. $p\le\sqrt n$
2. $\displaystyle\frac{n}{p}\in \mathbb Z_+,\frac{n}{p}\le\sqrt n$

所以我们枚举 $p$ 和 $\displaystyle\frac{n}{p}$，判断因数模拟即可。
时间复杂度为 $\Theta(\sqrt n)$，空间复杂度为 $\Theta(1)$。
:::::warning[坑点] 当 $p=\sqrt n$ 时 $p$ 和 $\displaystyle\frac{n}{p}$ 会算两次，要减去。
:::::

B. USB vs. PS/2：

:::::info[题目基本信息] 考察：贪心，排序，堆排序（$1400$）。
题目简介：
你有 $a+b+c$ 台电脑，$a$ 台只有 USB 端口，$b$ 台只有 PS\/2，$c$ 台两种都有。有 $m$ 个鼠标，他们分别能匹配 USB 或 PS\/2 端口（电脑和鼠标只能一一匹配），代价分别为 $\{val_m\}$，问在能匹配最多的电脑的情况下，这个值和最小代价分别是多少。
数据范围：

• $0\le a,b,c\le 10^5$
• $0\le m\le 3\times 10^5$ ::::: 注意到一个显然的贪心策略：优先匹配只能匹配一种端口的电脑。 :::::success[证明] 如果先将两种端口都可匹配的电脑匹配到 USB 鼠标上，那么后面可能出现的仅能匹配 USB 鼠标的电脑可能就因为缺少 USB 鼠标而无法匹配。
  PS\/2 端口同理。
  ::::: 所以我们优先按这个策略匹配，贪心地匹配 $val_i$ 较小的鼠标，可以使用排序或优先队列实现。
  时间复杂度为 $\Theta(a+b+c+m\log m)$，空间复杂度为 $\Theta(a+b+c+m)$。

C. Two strings：

:::::info[题目基本信息] 考察：二分，双指针。
题目简介：
给定字符串 $s,t$，从 $t$ 中删除一段最短子串，使得 $t$ 是 $s$ 的子序列，给出删除子串后的 $t$，若 $t$ 为空输出 -。
数据范围：

• $1\le |s|,|t|\le 10^5$ ::::: 先考虑完全暴力，枚举删除子串的左右端点，然后通过双指针（好吧好像也不是完全暴力）判断可行性，时间复杂度为 $\Theta(|t|^3)$。
  注意到删除一段子串后肯定剩下一段前缀和一段后缀，所以我们考虑对于每个前缀和后缀分别计算答案。
  设 $f_i$ 为 $t$ 的长度为 $i$ 的前缀作为子序列在 $s$ 中出现的最小右端点，$g_i$ 同上，只不过是反串在反串前缀中匹配，这个显然可以线性维护。
  然后显然最后的答案是在求最小值，且大于等于最小值的都可行，所以我们可以进行二分答案，二分最后的删除长度，然后枚举删除子串的左端点判断即可。
  时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

D. Maximum path：

:::::info[题目基本信息] 考察：贪心，动态规划 DP，DP 优化（$2300$）。
题目简介：
给定一个 $3\times n$ 的矩阵 $a_{i,j}$，这是每个格子的权值，每次你可以移动到你所在位置的四联通格，但不能重复经过同一个格子，问从 $(1,1)$ 到 $(3,n)$ 的所有路径上的格子的权值和最大是多少。
数据范围：

• $1\le n\le 10^5$
• $\forall i\in\{1,2,3\},j\in[1,n],|a_{i,j}|\le 10^9$ ::::: 注意到如果我们仍然像往常一样朴素设状态 $f_{i,j}$ 为走到 $(i,j)$ 格的路径权值和的最大值并且朴素转移的话，DP 就会出现后效性，我们注意到本题中矩阵是 $3\times n$ 的，$3$ 这个数或许会带来一些性质，我们不妨考虑优化状态转移方程。
  下面是一些性质：

1. 第 $1$ 行和第 $3$ 行本质是一样的，可以归为一类讨论。 :::::success[证明] 轴对称一下即可，显然成立。
   :::::

2. 当我们处于旁边两行时，我们不能往回走。 :::::success[证明] 注意到从旁边走回去后就回不来了，所以我们不能往回走。
   证毕。 :::::

3. 我们最多会连续往后走一格。 :::::success[证明]

   • 当连续往回走的步数为偶数格时：
     上面是唯一一种情况。
     容易发现它可以被如此替代：
   • 当连续往回走的步数为奇数格时： 容易发现它可以被如此替代：

   证毕。
   :::::

根据性质 2,3 可知，我们 DP 要讨论的情况数实际并不多，这时 DP 就没有后效性了。
时空复杂度均为 $\Theta(n)$。

E. Radio stations：

:::::info[题目基本信息] 考察：线段树，树状数组，cdq 分治。
题目简介：
给定 $n,k$ 以及 $\{x_n\},\{r_n\},\{f_n\}$，求满足下列条件的 $(i,j)$ 的个数：

• $1\le i<j\le n$
• $|x_i-x_j|\le\min(r_i,r_j)$
• $|f_i-f_j|\le k$

数据范围：

• $1\le n\le 10^5$
• $0\le k\le \color{red}10$
• $\forall i\in[1,n],1\le x_i,r_i\le 10^9$
• $\forall i\in[1,n],1\le f_i\le 10^4$ ::::: 注意到 $|x_i-x_j|\le\min(r_i,r_j)$ 条件中有 $\min$ 不好处理，所以我们可以将这些点按 $r_i$ 降序排序，这样就可以消掉 $\min$。
  然后注意到 $k\le 10$，所以我们可以对于每个 $f_i$ 分别处理贡献。
  那么现在我们需要支持单点修改区间查询和，由于值域为 $10^9$ 所以我们要上动态开点线段树。
  然后就做完了，数据结构好啊。
  时间复杂度为 $\Theta(nk\log V)$，空间复杂度为 $\Theta(n\log V)$。

F. Tree nesting：

:::::info[题目基本信息] 考察：图论，逆元，树形 DP，状压 DP（$2800$）。
题目简介：
给定两棵树 $S,T$，求 $S$ 有多少个连通子图与 $T$ 同构。
数据范围：

• $1\le |S|\le 1000$
• $1\le |T|\le\color{red}{12}$ ::::: 同构概念
  注意到 $|T|\le 12$，考虑状压 dp。
  同时又在树上做，考虑树形 dp。
  注意到题目问的是 $S$ 到 $T$ 的同构子图数，而不是 $S$ 的同构子图到 $T$ 的总同构数，直接 dp 肯定会算重。 :::::success[解决方案] 显然，$S$ 的所有同构子图到 $T$ 的同构数都相同，都是 $T$ 到 $T$ 的同构数。
  所以我们要求 $S$ 到 $T$ 的同构子图数，不妨求出 $S$ 的同构子图到 $T$ 的总同构数，再除以 $T$ 到 $T$ 的同构数。
  ::::: 那么现在我们要求 $S$ 的同构子图到 $T$ 的总同构数和 $T$ 到 $T$ 的同构数，容易发现两者可以用类似的方法做，不妨以求 $S$ 的同构子图到 $T$ 的总同构数为例。
  猜测时间复杂度是 $\Theta(|S||T|2^{|T|})$ 的。
  钦定 $S$ 为有根树，根为 $1$，$T$ 为无根树，不妨设 $f_{u_s,T',u_t}$ 为在 $S$ 上以 $u_s$ 为根的子树的所有连通子图（必包含 $u_s$）同构到 $T$ 上以 $u_t$ 为根的集合为 $T'$ 的连通子图的总同构数。
  为了方便求 $f_{u_s,T',u_t}$，我们不妨预处理出在 $T$ 上对于每个点为根时每个子节点的子树内节点构成的集合，以 $u$ 为根子节点为 $v$ 时 $v$ 子树内的节点集合记为 $g_{u,v}$，记 $S$ 和 $T$ 的 $u$ 的邻边集合为 $gs_u$ 和 $gt_u$。
  显然 $S$ 的一个点可以同构到 $T$ 的一个点，所以初始时要令 $f_{u,\{v\},v}\leftarrow 1$，然后状态转移方程式就为： $$f_{us,T',ut}\leftarrow f_{us,T',ut}+\sum_{vs\in gs_{us}}\sum_{vt\in gt_{ut}}f_{us,\complement_{T'}(T'\cap g_{ut,vt}),ut}\times f_{vs,T'\cap g_{ut,vt},vt}$$ 注意这里是为了方便展示状态转移方程，为了防止后效性，枚举顺序如下：

1. dfs 枚举 $us$。
2. 枚举 $vs\in gs_{us}$。
3. 枚举 $T'$，从大到小枚举。
4. 枚举 $ut$。
5. 枚举 $vt$。

这样最后答案就是 $\displaystyle ans\leftarrow\sum_{i=1}^{|S|}\sum_{j=1}^{|T|}f_{i,\bigcup_{p=1}^{|S|}\{p\},j}$。
然后对两个问题分别做一遍，用快速幂算答案即可。
时空复杂度均为 $\Theta(|S||T|2^{|T|})$。
:::::warning[坑点] 本题相当卡空间，尽量少开 long long。
:::::