巅峰赛34题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫的宝石容器 普及− T2 午枫的城市路线 普及/提高− T3 午枫的对称字符 普及/提高− T4 午枫的小队评分 普及/提高− T5 午枫的平衡调整 普及/提高− T6 午枫的路线封闭 普及+/提高
T1 午枫的宝石容器
题目大意
有 nnn 颗宝石，大小为 AiA_iAi ，以及 n−1n-1n−1 个容器，容量为 BiB_iBi 。现在可以额外购买一个容量为 xxx 的容器，使得总共有 nnn 个容器。要求每个容器最多放一颗宝石，且宝石大小不超过容器容量。求最小的 xxx 使得所有宝石都能放入容器中，若无法实现输出 −1-1−1。
题解思路
贪心匹配即可。为了尽量让大的宝石优先匹配大的容器，先将宝石数组 aaa 和容器数组 bbb 都按从大到小排序。
然后用双指针从大到小匹配：指针 iii 枚举宝石，指针 jjj 枚举容器。如果当前宝石 ai≤bja_i \le b_jai ≤bj ，说明可以用这个容器装下，指针 jjj 向后移动；否则说明当前宝石无法被任何已有容器容纳，只能依赖新买的容器，于是记录这个宝石。
统计这种“装不下”的宝石个数：
* 如果为 000，说明原有容器已经够用，此时新容器可以取最小值，即 ana_nan ；
* 如果为 111，说明只有一个宝石需要新容器，答案就是这个宝石的大小；
* 如果超过 111，说明至少有两个宝石需要新容器，但我们只能买一个，因此无解。
这个贪心是正确的，因为总是优先让大宝石匹配大容器，可以保证不会浪费容量。
时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。
参考代码
T2 午枫的城市路线
题目大意
给定一张有向图，从节点 111 出发，问是否存在一条路径可以回到节点 111（即形成一个包含 111 的环）。如果存在，求这样的路径中边数最少的一条长度；否则输出 −1-1−1。
题解思路
由于所有边权为 111，要求最短路径，直接使用 BFS。
从节点 111 出发进行广度优先搜索，用数组 d[i]d[i]d[i] 记录从 111 到达节点 iii 的最短距离。每次从队列中取出一个节点，遍历它的所有出边，如果某个节点还没访问过，就更新距离并入队。
在 BFS 过程中，如果某条边可以从当前节点走回 111，那么就找到了一个回环，其长度就是当前节点的距离加 111。由于 BFS 按层扩展，第一个找到的回环一定是最短的。
如果最终没有办法回到 111，说明不存在这样的路径，输出 −1-1−1。
时间复杂度为 O(n+m)O(n+m)O(n+m)。
参考代码
T3 午枫的对称字符
题意简述
给定一个仅由大写英文字母组成的字符串 SSS，要求计算三元组 (i,j,k)(i,j,k)(i,j,k) 的数量，使得 1≤i<j<k≤∣S∣1 \le i < j < k \le |S|1≤i<j<k≤∣S∣ 且 SiSjSkS_iS_jS_kSi Sj Sk 是回文串。由于长度为 333 的回文串唯一的条件是首尾字符相同，即 Si=SkS_i = S_kSi =Sk ，中间字符可以是任意字符，因此本题实质上就是统计所有首尾字符相同的三元组数量。
解题思路
可以采用前缀计数的方法，遍历字符串时维护一个数组记录每个字母已经出现的次数，同时维护一个数组记录以每个字母为首字符的可形成组合数量。在遍历每个字符作为中间字符时，将当前字符对应的组合数量累加到结果中，然后更新以每个字母为首字符的组合数量，最后更新当前字符的出现次数。这样就能在一次遍历中统计出所有满足条件的三元组，时间复杂度为 O(n⋅26)O(n \cdot 26)O(n⋅26)，空间复杂度为 O(26)O(26)O(26)，足够应对 ∣S∣≤2×105|S| \le 2 \times 10^5∣S∣≤2×105 的情况。
参考代码
T4 午枫的小队评分
题意简述
有 NNN 名选手，每位选手都有实力值 AiA_iAi 和消耗值 BiB_iBi 。需要从中选出一个大小为 KKK 的小队 SSS，小队评分定义为：
score(S)=(maxi∈SAi)×(∑i∈SBi)\text{score}(S) = \left(\max_{i \in S} A_i\right) \times \left(\sum_{i \in S} B_i\right) score(S)=(i∈Smax Ai )×(i∈S∑ Bi )
目标是选择一个小队，使得评分尽可能小，并输出最小评分。
解题思路
首先将选手按照实力值 AiA_iAi 从小到大排序。然后考虑当某个选手 iii 的实力值成为小队中最大实力值时，如何选择另外 K−1K-1K−1 名选手以使得消耗值之和最小。为了高效计算，可以使用一个大根堆维护当前已选择的 K−1K-1K−1 个消耗值最大的选手，如果当前堆中超过 K−1K-1K−1 个元素，就弹出最大的，这样保证堆中始终保存消耗值最小的 K−1K-1K−1 个候选成员。每遍历一个选手，将其作为最大实力值候选时，累加堆中消耗值与自身消耗值，然后计算评分并更新最小值。这样遍历一次即可得到最优解，时间复杂度为 O(NlogK)O(N \log K)O(NlogK)，空间复杂度为
O(K)O(K)O(K)。
参考代码
T5 午枫的平衡调整
题意简述
给定 NNN 名成员，每名成员属于三个小组之一并有一个贡献值。希望通过调整部分成员的小组归属，使得三个小组的总贡献值完全相等。每次调整只能将某个成员移动到另一个已有的小组中，目标是判断是否可以实现平衡，如果可以，则输出最少需要调整的人数，否则输出 −1-1−1。
解题思路
首先计算所有成员贡献值之和，如果不能被 333 整除，则无法实现平衡，直接输出 −1-1−1。设每组的目标贡献值为总和的三分之一。使用三维动态规划，状态为 dp[i][j][k]dp[i][j][k]dp[i][j][k]，表示前 iii 个成员中，第一组总贡献为 jjj，第二组总贡献为 kkk 时所需的最少调整人数。遍历每个成员时，可以选择将其分配到任意一组，累加调整次数（若成员当前组与选择组不同则加一），更新状态。最终 dp[N][target][target]dp[N][target][target]dp[N][target][target]
即为最少调整人数，如果无法达到则为无穷大，输出 -1。
参考代码
T6 午枫的路线封闭
题意简述
给定 NNN 个地点和 MMM 条双向路线，每条路线有通行代价。随后有 QQQ 个操作，包含封闭某条路线或询问两点间最小通行代价。封闭操作总次数不超过 300300300。要求按操作顺序处理，每次询问输出当前未封闭路线下的最短路径，若无法到达输出 −1-1−1。
解题思路
由于地点数量 N≤300N \le 300N≤300，可以使用 Floyd 算法处理所有点对最短路径。关键是封闭操作较少，因此可以采用离线处理策略：先将所有封闭操作标记，并从最终状态的图出发，计算全局最短路径。然后逆序处理操作序列，每遇到一次封闭操作就“恢复”对应边，并更新受影响的最短路径；遇到查询操作直接读取当前最短路径表即可。这样只需在逆序处理时更新路径，而不必每次从头计算，保证在 O(N3+Q)O(N^3 + Q)O(N3+Q) 时间内完成。最终按正序输出查询结果即可。
参考代码
