跳转至

算法周赛round26

T1

知识点：枚举，质数判定。

由于 $n $ 最多只有一万，因此直接从 $1 $ 到 $n$ 枚举判断每个数是否为孤独数是完全可行的。

算法步骤

  1. 从大到小枚举 $i=n,n-1,\dots,1$（这样在找到第 $k$ 个时即可立即返回）。
  2. 对每个 $i$：
    • 判断是否为质数；
    • 判断是否满足 $i \equiv r \pmod m$。
  3. 若两者均满足，则计数器加一。
  4. 当计数器等于 $k$ 时，输出当前的 $i$。

如果循环结束仍未找到第 $k$ 个孤独数，则输出 $-1$。

时间复杂度：$O(n\sqrt{n})$

T2

知识点：字符串。

思路分析

题目允许的操作是：

选择一个位置 $i$（$1 \leq i < n$），将 $s_i$ 修改为 $s_{i+1}$。

也就是说，你只能把某个字符变成它右边那个字符，不能随便改成任意字符。

因此，如果我们把操作不断向左传播：

  • $s_{n-1}$ 可以变成 $s_n$
  • $s_{n-2}$ 可以变成 $s_{n-1}$，也可以进一步经过传播变成 $s_n$
  • ...
  • 最终，每个字符都可以被修改成 最终靠右传递而来的一连串值

从这个传播链可以看到：

最终字符串中所有字符的值必定等于 $s_n$

原因：

  • 因为最右端的字符 $s_n$ 无法被改变；
  • 左边的位置只能被“推”成右边已有的值；
  • 所以最后所有字符只能变成 $s_n$。

因此不需要尝试任何其他目标字符，最终形态完全确定。

如何计算最少操作次数？

我们希望把所有字符都变成 $s_n$。

  • 若某个字符位置的值已经是 $s_n$，则无需操作。
  • 若不是 $s_n$，就必须通过一系列传播操作使它变成 $s_n$。

结论：

只需要数出有多少个字符已经等于 $s_n$，其余的都需要改变。

因此答案为 $n-cnt[s_n]$。其中 $cnt[s_n]$ 表示字符 $s_n$ 的个数。

时间复杂度：$O(n)$。

T3

知识点：字符串，计数。

思路分析

条件 1：字符串本身是否包含 26 个不同字符

直接使用计数数组或布尔数组统计字符种类数：

  • 若种类数恰好为 $26$，则满足条件 $1$；
  • 否则不满足。

时间复杂度：$O(n)$

条件 2：是否存在真子串也包含全部 $26$ 个字母

思考：哪些子串有可能仍然包含所有 $26$ 个字母？

如果一个子串仍然拥有全部 $26$ 个不同字符，那么它必须不缺失原串中出现次数为 $1$ 的字符。

因此我们只需要检查：

只删除一个字符（即删掉开头或结尾）后，剩余子串是否依然包含全部 26 个字符？

理由：

  • 真子串必须至少去掉一个字符；
  • 若去掉中间字符，那相当于去掉某个位置，但如果它不是唯一出现的某字符，则不会影响种类数；

  • 最极端地，只检查：

  • 去掉 $s_1$ 的子串 $s[2..n]$

  • 去掉 $s_n$ 的子串 $s[1..n-1]$

即可覆盖所有可能减少最少字符的情况。

因此条件 $2$ 的判定为：

  • 是否 $cnt[s[1]] \geq 2$ 或 $cnt[s[n]] \geq 2$。

时间复杂度：$O(n)$。

T4

知识点：动态规划

子任务 1（暴力枚举）

当 $n \le 20$ 时，可以枚举所有划分方式。

  • 每两个相邻橙子之间有“切”或“不切”两种选择；
  • 总方案数：$2^{n-1}$。

对每种方案计算所有段的成本，取最小值。

时间复杂度：

\[ O(2^n \cdot n) \]

子任务 2、3（动态规划）

对于一般情况（$n \le 2\times 10^4$），必须使用 DP。

（1）DP 定义

设：

\[ dp[i] = \text{装完前 } i \text{ 个橙子的最小成本} \]

答案为：

\[ dp[n] \]

初始化：

\[ dp[0] = 0 ,\quad dp[i]=+\infty,\texttt{其中}\ i\in [1,n] \]

（2）转移

最后一个箱子的区间是 $[j, i]$，长度为：$s = i - j + 1 \le m$

转移方程：

\[ dp[i] = \min_{j \le i, i-j+1 \le m} \left( dp[j-1] + k + s \times (\max(a_j..a_i) - \min(a_j..a_i)) \right) \]

（3）维护区间最大值 / 最小值

对于固定的右端点 $i$，枚举所有合法的左端点 $j$：

倒序枚举 $j$，由于每次向左扩展，只需更新 max/min 为当前值与新加入的 $a[j]$ 之间的最大 / 最小值，维护成本为 $O(1)$。

（4）时间复杂度 $O(nm)$

T5

知识点：最短路，数学。

关键观察

1. A 的路线和 B 的路线必须是两条最短路

因为：

  • 额外加权不会改变真实图结构，只改变时间。
  • 如果走一条较长路径，肯定不如花钱加权短路径上的边更经济。
  • 因此两人一定都走各自的无权最短路（边数最少的路径）。

若某人不可达，则答案为 $-1$。

之后只需要考虑： 如何使用 $k$ 元钱加速两条固定路径（长度分别为 LenA、LenB）上的边。

数学部分：如何最优使用 k？

某条边走一次，若给它提升 $t$ 次，则时间为：

\[ T = \frac{1}{1+t} \]

耗费 $t$ 元，收益：

\[ 1 - \frac{1}{1+t} \]

最优策略：尽可能让所有边的 $(1+t_i)$ 接近。

也就是说：

  • 令 S = 总边数（两条最短路的边数总和）
  • 先给每条边平均分配 $\lfloor k/S\rfloor$ 次加成
  • 再把剩余 $k\bmod S$ 个单位逐个分配给任意边（每多加 $1$ 单位收益最大）

最终某路径的总时间为：

设某条边加了 $c_i$ 次，则：

\[ T = \sum_{i=1}^S \frac{1}{1+c_i} \]

其中：

  • 设 base = $\lfloor k/S \rfloor$
  • rem = $k\bmod S$
  • 则有 rem 条边的增量为 $base+1$，其余为 $base$
\[ T = rem \cdot \frac{1}{base+2} + (S - rem)\cdot \frac{1}{base+1} \]

实现步骤

  1. BFS 求 A 的最短路长度 LenA
  2. BFS 求 B 的最短路长度 LenB
  3. 若不可达 → 输出 $-1$
  4. $S = LenA + LenB$
  5. 若 $S = 0 →$ 输出 $0$
  6. 按上述公式计算最小时间
  7. 考虑两条路径若共享边，需加入排队等待时间（可忽略边分配，直接按次序累加）

但由于走完边立即重置权值 $→$ 排队不会改变最优性，只在最后累加等待时间。

复杂度

  • BFS 求最短路：$O(n+m)$
  • 计算结果：$O(1)$

总时间：

\[ O\bigl(\sum(n+m)\bigr) \le 2.5\times 10^6 \]

核心：两条路径长度固定后，最优增权策略是尽可能均匀地把 k 分配到 S 条边上。

最终：

设

\[ S = dis(x_1,y_1) + dis(x_2,y_2) \]

若不可达，则输出 $-1$。

否则：

\[ base = \left\lfloor \frac{k}{S} \right\rfloor \]
\[ rem = k \bmod S \]
\[ ans = rem\cdot \frac{1}{base+2} + (S-rem)\cdot \frac{1}{base+1} \]