ACGO 巅峰赛#14 题解
写在前面
> 本场比赛 F. 可变数组 现已恢复评测。
本场排位赛的所有题目的难度评级为：
题目编号 题目标题 难度 A. 混淆字符串 入门 B. 循环小数 普及- C. 特殊的染料 普及- D. 君往何处 普及/提高- E. 万圣糖果 普及+/提高 F. 可变数组 普及+/提高
非常感谢大家参加本场巅峰赛！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解简述
以下提供每道题目的思路简述，详细题解的AC代码包括复杂度分析，请点击题目标题查看。
A - 混淆字符串
字符串；模拟
将给出的两个字符串 SSS 和 TTT 中的所有混淆字符，转化为同一种格式，再比较即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B - 循环小数
数学；模拟
我们使用以下方法来得出 pq\dfrac{p}{q}qp 的循环序列：
1. 进行除法：将 p 作为被除数，不断乘 101010 除以 qqq。
2. 记录余数和商：每次除法后会得到一个商和一个新的余数，将商依次记录下来，并对余数继续按照步骤 111 处理。
3. 重复步骤 111 和 222，当计算出的余数为一开始的 ppp 时，说明结束了一轮完整的循环。记录的商的序列即为 pq\dfrac{p}{q}qp 的循环序列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C - 特殊的染料
模拟；枚举
采用冒泡排序的方法，每次进行交换的时候，枚举 kkk，找到费用最低的满足条件的 kkk，并累计答案即可。
时间复杂度 O(N3)\mathrm{O}(N^3)O(N3)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D - 君往何处
枚举；贪心
从小到大枚举使用的手指数量；
对于枚举的手指数量为 XXX，存储每个手指下一次可以点击音符的最早时间 a1,a2,⋯ ,aXa_1, a_2, \cdots, a_Xa1 ,a2 ,⋯,aX ，遍历所有的音符，对于每个到来的音符 iii 使用选择手指 jjj 满足 aj=min(a1,a2,⋅,aX)a_j = \min{(a_1, a_2, \cdot, a_X)}aj =min(a1 ,a2 ,⋅,aX )，来尝试点击这个音符，并且尽可能早地点击这个音符，即 max(aj,ti−30)\max{(a_j, t_i - 30)}max(aj ,ti −30)。这样我们便可以保证在使用 XXX
个手指的情况下，使得每个音符都可以在允许的最早的时刻被点击。
时间复杂度 O(N)\mathrm{O}(N)O(N)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E - 万圣糖果
动态规划；状态DP
考虑进行状态DP，并从前到后考虑所有礼盒，那么会涉及到 666 种状态。
1. 未使用魔法，礼盒中的糖果数量状态为 AAA。
2. 使用 111 次魔法，礼盒中的糖果状态为 BBB。
3. 使用 111 次魔法，礼盒中的糖果状态为 AAA（即第一次使用魔法的区间结束了）。
4. 使用 222 次魔法，礼盒中的糖果状态为 CCC。（即和第一次使用魔法的区间重合的部分）
5. 使用 222 次魔法，礼盒中的糖果状态为 BBB。（即第和第一次使用魔法的区间不重合的部分）
6. 使用 222 次魔法，礼盒中的糖果状态为 AAA。（即两次使用魔法的区间全部结束）
令 dp0,dp1,⋯ ,dp5dp_0, dp_1, \cdots, dp_5dp0 ,dp1 ,⋯,dp5 分别对应以上 666 种状态下前 iii 个礼盒能够拿到的最多的糖果的数量；那么有以下关系转移方式。
令 dpIdpIdpI 为前 iii 个礼盒能够拿到的最多的糖果的数量，讨论如何从前 i−1i - 1i−1 个礼盒能够拿到的最多的糖果数量 dpdpdp 转移到 dpIdpIdpI。
1. dpI0=dp0+aidpI_0 = dp_0 + a_idpI0 =dp0 +ai
2. dpI1=max(dp0,dp1)+bidpI_1 = \max{(dp_0, dp_1)} + b_idpI1 =max(dp0 ,dp1 )+bi
3. dpI2=max(dp1,dp2)+aidpI_2 = \max{(dp_1, dp_2)} + a_idpI2 =max(dp1 ,dp2 )+ai
4. dpI3=max(dp0,dp1,dp3)+cidpI_3 = \max{(dp_0, dp_1, dp_3)} + c_idpI3 =max(dp0 ,dp1 ,dp3 )+ci
5. dpI4=max(dp2,dp3,dp4)+bidpI_4 = \max{(dp_2, dp_3, dp_4)} + b_idpI4 =max(dp2 ,dp3 ,dp4 )+bi
6. dpI5=max(dp3,dp4,dp5)+aidpI_5 = \max{(dp_3, dp_4, dp_5)} + a_idpI5 =max(dp3 ,dp4 ,dp5 )+ai
最终 max(dp0,dp1,⋯ ,dp5)\max{(dp_0, dp_1, \cdots, dp_5)}max(dp0 ,dp1 ,⋯,dp5 ) 便是答案。
时间复杂度 O(N)\mathrm{O}(N)O(N)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F - 可变数组
线段树；二分查找；
详情参考 ACL｜通用「线段树」模板
定义二元运算符 op 和单位元 e。
使用数组 AAA，构建线段树，时间复杂度 O(N)\mathrm{O}(N)O(N)。
1. 对于赋值操作我们直接使用 sgt.set(int p, T x)，时间复杂度 O(logN)\mathrm{O}(\log{N})O(logN)。
2. 对于交换操作，和赋值操作类似，先使用 sgt.get(int p) 操作获取 ALA_LAL 和 ARA_RAR 的值，时间复杂度 O(1)\mathrm{O}(1)O(1)；然后再使用 sgt.set(int p, T x) 操作，时间复杂度 O(logN)\mathrm{O}(\log{N})O(logN)。
3. 查询区间最大值，使用 sgt.prod(l, r) 操作得出，时间复杂度 O(logN)\mathrm{O}(\log{N})O(logN)。
4. 在线段树上二分查找，使用 sgt.max_right(int l)，若返回值大于 RRR 则输出 −1-1−1，否则输出答案。时间复杂度 O(logN)\mathrm{O}(\log{N})O(logN)。
总的时间复杂度 O(N+QlogN)\mathrm{O}(N + Q\log{N})O(N+QlogN)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
