ACGO欢乐赛15题目解析
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1 ZXC的探险计划
题目大意
一条数轴上有两个整数，从原点出发每次移动一格，最少几次移动能到达两个整数。
题目思路
题目本身比较好理解，只需要注意不同的情况即可。
* 初步的想法是，如果a、b两个数字在原点同侧，只需要先到距离原点近的，再到远的即可；如果a、b两个数字在原点两侧则只需要依次到达两个数字即可。
* 进而我们想到，其实无论什么情况，都可以认为是先到两者距离原点近的，在经过两点之间的长度到达另一点。如此做法就可以避免判断，简化代码，直接计算即可。
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2 子序列转换
题目大意
给定一个序列，通过对原始序列进行操作，判断最终能否变成一个不下降序列。
题目思路
首先要针对题目的核心操作进行分析，经过分析后发现，操作其实就是将选中序列[ai,aj][a_i,a_j][ai ,aj ]倒置，因此我们可以想到冒泡排序或者选择排序，当kkk大于等于222时，经过操作一定是可以达到目标的，并且如果kkk为1，序列本身成不下降序列也是满足要求的。
时间复杂度分析
该算法的时间复杂度主要就是单层循环，因此是 O(n)O(n)O(n) 的复杂度。
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3 捞薯条
题目大意
nnn箱薯条，选择nk\frac{n}{k}kn 辆卡车来运输，每辆卡车运输连续的kkk箱薯条，求在所有可行的情况下，卡车最大载重和最小载重的差值。
题目思路
根据题意，每辆卡车必须装满kkk箱，且卡车数是nk\frac{n}{k}kn ，所以卡车数辆必须是nnn的约数。所以枚举每一个iii，代表车辆装载连续的iii箱，然后求出当下情况载重的最大差值。
考虑到要多次计算连续的一段的和，所以可以使用前缀和进行优化，降低计算区间和的时间复杂度。
时间复杂度分析
该算法的时间复杂度主要集中在枚举每个nnn的约数，然后统计序列中每段连续的nnn个数，然后求极差。解决问题函数时间复杂度在有前缀和优化后几乎等于 O(n)O(n)O(n) 。
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4 或矩阵
题目大意
当前有一个矩阵MMM，需要判定当前矩阵是否存在可以通过指定方式变换而来。变换的方式是M(i,j)M_{(i,j)}M(i,j) 是由aia_iai |aja_jaj 所得。
题目思路
根据题意，如果存在一个序列aaa按照指定方式变换成目标矩阵，那我们可以分析得到如下操作:
aia_iai 这个位置只会影响到M(i,j)M_{(i,j)}M(i,j) 和M(i,j)M_{(i,j)}M(i,j) ,所以我们将aia_iai 转换为二进制，并且假设每一位上都是111。
因为aia_iai 上最多只能存在格子M(i,j)M_{(i,j)}M(i,j) 和格子M(i,j)M_{(i,j)}M(i,j) 二进制下存在的1，所以把两个格子的数值依次跟aia_iai 进行&运算即可。最后验证是否可以变成指定矩阵即可。
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5 音乐先辈YUILICE
题目大意
根据序列中的aia_iai 得到2ai2^{a_i}2ai 记为AAA，再找对应的aja_jaj ，得到2aj2^{a_j}2aj 记为BBB，如果ABA^BAB=BAB^ABA,则认为找到了一组答案。
题目思路
1. 读入每个样例的乐谱数据数量 nnn。
2. 使用 map 存储每个地址 AAA 的出现次数。
3. 遍历 map，对于每个地址 AAA，如果其出现次数大于等于2，计算能够组成的按键地址数量并累加。这个循环遍历map中的每个元素（即每个不同的aia_iai 及其出现次数）。如果某个 aia_iai 出现了至少两次（i.second >= 2），那么它可以与自己组合成完整的地址。组合数可以通过组合公式 C(n, 2) = n(n-1) / 2计算，即从这些重复的 aia_iai 中选择两个不同的进行组合。
4. 特殊情况。对于 aia_iai = 111 和aja_jaj = 222，它们对应的地址 AAA = 212^121 = 222 和 BBB = 222^222 = 444 满足$ A^B$ = BAB^ABA。因此，如果输入中有 111 和 222，那么它们之间可以相互配对。配对的总数是它们出现次数的乘积。
5. 输出最终的按键地址数量。
算法核心思想是通过 map 存储地址 AAA 的出现次数，然后遍历 map 计算满足条件的按键地址数量。最后输出结果。
时间复杂度分析
该算法的时间复杂度主要取决于遍历和统计 map 的操作，因此是 O(n)O(n)O(n) 的复杂度。
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6接力长跑
题目大意
再给定序列中，找满足条件的连续数值最大为多少。
题目思路
其中连续的数字要想累加，需要满足前后两个数的奇偶性想法才可以累加。同时因为学生们能力值存在负数，所以还需要考虑是否放弃该同学即前面内容。在整个过程中全程判断是否存在更优的情况，如果存在及时记录即可。该问题属于线性动态规划经典问题变形。
我们可以设定学生状态为dp[i]dp[i]dp[i]，从而列出以下状态转移方程
* aia_iai % 2 != ai−1a_{i-1}ai−1 % 2 : dp[i]=max(a[i],dp[i−1]+a[i])dp[i] = max(a[i],dp[i-1] + a[i])dp[i]=max(a[i],dp[i−1]+a[i])
时间复杂度分析
该算法的时间复杂度主要集中在遍历序列中每一项，因此是 O(n)O(n)O(n) 的复杂度。
代码演示
