CF762(EDU17) 题解

zrl123456 · 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。
:::::