官方题解｜巅峰赛#14

アイドル

2024-11-11 13:47:02

发布于：浙江

47阅读

0回复

0点赞

ACGO 巅峰赛#14 题解

写在前面

本场比赛 F. 可变数组现已恢复评测。

本场排位赛的所有题目的难度评级为：

题目编号	题目标题	难度
A.	混淆字符串	入门
B.	循环小数	普及-
C.	特殊的染料	普及-
D.	君往何处	普及/提高-
E.	万圣糖果	普及+/提高
F.	可变数组	普及+/提高

非常感谢大家参加本场巅峰赛！

题解简述

以下提供每道题目的思路简述，详细题解的AC代码包括复杂度分析，请点击题目标题查看。

A - 混淆字符串

字符串；模拟

将给出的两个字符串 $S$ 和 $T$ 中的所有混淆字符，转化为同一种格式，再比较即可。

B - 循环小数

数学；模拟

我们使用以下方法来得出 $\dfrac{p}{q}$ 的循环序列：

进行除法：将 p 作为被除数，不断乘 $10$ 除以 $q$ 。
记录余数和商：每次除法后会得到一个商和一个新的余数，将商依次记录下来，并对余数继续按照步骤 $1$ 处理。
重复步骤 $1$ 和 $2$ ，当计算出的余数为一开始的 $p$ 时，说明结束了一轮完整的循环。记录的商的序列即为 $\dfrac{p}{q}$ 的循环序列。

C - 特殊的染料

模拟；枚举

采用冒泡排序的方法，每次进行交换的时候，枚举 $k$ ，找到费用最低的满足条件的 $k$ ，并累计答案即可。

时间复杂度 $\mathrm{O}(N^3)$ 。

对于枚举的手指数量为 $X$ ，存储每个手指下一次可以点击音符的最早时间 $a_1, a_2, \cdots, a_X$ ，遍历所有的音符，对于每个到来的音符 $i$ 使用选择手指 $j$ 满足 $a_j = \min{(a_1, a_2, \cdot, a_X)}$ ，来尝试点击这个音符，并且尽可能早地点击这个音符，即 $\max{(a_j, t_i - 30)}$ 。这样我们便可以保证在使用 $X$ 个手指的情况下，使得每个音符都可以在允许的最早的时刻被点击。

时间复杂度 $\mathrm{O}(N)$ 。

E - 万圣糖果

动态规划；状态DP

考虑进行状态DP，并从前到后考虑所有礼盒，那么会涉及到 $6$ 种状态。

未使用魔法，礼盒中的糖果数量状态为 $A$ 。
使用 $1$ 次魔法，礼盒中的糖果状态为 $B$ 。
使用 $1$ 次魔法，礼盒中的糖果状态为 $A$ （即第一次使用魔法的区间结束了）。
使用 $2$ 次魔法，礼盒中的糖果状态为 $C$ 。（即和第一次使用魔法的区间重合的部分）
使用 $2$ 次魔法，礼盒中的糖果状态为 $B$ 。（即第和第一次使用魔法的区间不重合的部分）
使用 $2$ 次魔法，礼盒中的糖果状态为 $A$ 。（即两次使用魔法的区间全部结束）

令 $dp_0, dp_1, \cdots, dp_5$ 分别对应以上 $6$ 种状态下前 $i$ 个礼盒能够拿到的最多的糖果的数量；那么有以下关系转移方式。

令 $dpI$ 为前 $i$ 个礼盒能够拿到的最多的糖果的数量，讨论如何从前 $i - 1$ 个礼盒能够拿到的最多的糖果数量 $dp$ 转移到 $dpI$ 。

$dpI_0 = dp_0 + a_i$
$dpI_1 = \max{(dp_0, dp_1)} + b_i$
$dpI_2 = \max{(dp_1, dp_2)} + a_i$
$dpI_3 = \max{(dp_0, dp_1, dp_3)} + c_i$
$dpI_4 = \max{(dp_2, dp_3, dp_4)} + b_i$
$dpI_5 = \max{(dp_3, dp_4, dp_5)} + a_i$

最终 $\max{(dp_0, dp_1, \cdots, dp_5)}$ 便是答案。

时间复杂度 $\mathrm{O}(N)$ 。

F - 可变数组

线段树；二分查找；

详情参考 ACL｜通用「线段树」模板

定义二元运算符 op 和单位元 e。

int op(int a, int b) {return std::max(a, b);};
int e() {return 0;};

使用数组 $A$ ，构建线段树，时间复杂度 $\mathrm{O}(N)$ 。

Segtree<int, op, e> sgt(a);

对于赋值操作我们直接使用 sgt.set(int p, T x)，时间复杂度 $\mathrm{O}(\log{N})$ 。
对于交换操作，和赋值操作类似，先使用 sgt.get(int p) 操作获取 $A_L$ 和 $A_R$ 的值，时间复杂度 $\mathrm{O}(1)$ ；然后再使用 sgt.set(int p, T x) 操作，时间复杂度 $\mathrm{O}(\log{N})$ 。
查询区间最大值，使用 sgt.prod(l, r) 操作得出，时间复杂度 $\mathrm{O}(\log{N})$ 。
在线段树上二分查找，使用 sgt.max_right(int l)，若返回值大于 $R$ 则输出 $-1$ ，否则输出答案。时间复杂度 $\mathrm{O}(\log{N})$ 。