挑战赛30题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 小午的家族谱 入门 T2 午枫的卡片匹配游戏 普及- T3 午枫的登山挑战 普及- T4 午枫的积分记录 普及/提高- T5 午枫的涂色游戏 普及/提高- T6 午枫的排列 普及/提高-
T1 小午的家族谱
题目大意
给定一棵以 111 为根的家族树，每个人只有一个父亲，且父亲编号比自己小，求从编号为 nnn 的小午一路向上追溯到编号为 111 的午枫，一共经过多少代。
题解思路
由于每个人的父亲编号都小于自己，其实已经隐含给出了一条从 nnn 指向 111 的唯一链。要求的代数就是这条链的长度。最直接的做法是从 nnn 开始，不断跳到它的父亲 pnp_npn ，再跳到父亲的父亲，一直走到编号为 111 为止，每走一步就把答案加一。因为保证最终一定能到达 111，而且每次编号都会变小，所以循环次数最多是 nnn 次，复杂度是 O(n)O(n)O(n)，在数据范围内完全没有问题。
参考代码
T2 午枫的卡片匹配游戏
题目大意
给定一个长度为 nnn 的数组 aaa，统计有多少对下标 (i,j)(i,j)(i,j)（1≤i<j≤n1 \le i < j \le n1≤i<j≤n），使得 min(ai,aj)=i\min(a_i,a_j)=imin(ai ,aj )=i 且 max(ai,aj)=j\max(a_i,a_j)=jmax(ai ,aj )=j。
题解思路
题目条件等价于：第 iii 张和第 jjj 张卡片上的数字正好是 {i,j}\{i,j\}{i,j} 这一对。于是只会有两种情况。第一种是两张卡片都放在了“正确位置”，也就是 ai=ia_i=iai =i 且 aj=ja_j=jaj =j，只要数出所有满足 ax=xa_x=xax =x 的位置个数，任取两个就能组成一个合法的卡片对，这一部分直接用组合数计算即可。第二种情况是成对互换，即 ai=ja_i=jai =j 且 aj=ia_j=iaj =i，这种每一对只能算一次，从前往后扫数组，用一个标记数组避免重复统计即可。把这两类情况的数量加起来就是答案，整体只需要线性扫描，时间复杂度是
O(n)O(n)O(n)。
参考代码
T3 午枫的登山挑战
题目大意
从营地 111 出发，初始体力为 TTT，每次从营地 iii 走到 i+1i+1i+1 需要消耗 AiA_iAi 点体力，到达部分营地时可以恢复体力，问在体力始终大于 000 的前提下，是否能够到达营地 NNN。
题解思路
这条登山路线本身就是一条从 111 到 NNN 的直线，没有任何选择分支，因此可以直接按顺序模拟整个过程。用一个变量记录当前体力值，从营地 111 开始依次向前走，每次先减去对应的体力消耗，如果减完后体力小于等于 000，就说明无法继续前进，可以直接输出 No。如果成功到达下一个营地，再检查这个位置是否有补给点，有的话就把体力加上去。由于补给点的位置是按编号递增给出的，用一个指针顺序处理即可。只要能顺利走到营地 NNN，中途没有失败，就输出 Yes。整个过程只需一次遍历，时间复杂度为 O(N+M)O(N+M)O(N+M)。
参考代码
T4 午枫的积分记录
题目大意
给定一个长度为 nnn 的整数序列 aaa，统计有多少个连续区间 [l,r][l,r][l,r]，使得区间和 ∑i=lrai\sum_{i=l}^r a_i∑i=lr ai 能被 MMM 整除。
题解思路
这是一个典型的前缀和取模问题。设前缀和 si=a1+a2+⋯+ais_i=a_1+a_2+\dots+a_isi =a1 +a2 +⋯+ai ，那么区间 [l,r][l,r][l,r] 的和可以表示为 sr−sl−1s_r-s_{l-1}sr −sl−1 。这个值能被 MMM 整除，当且仅当 sr mod M=sl−1 mod Ms_r \bmod M = s_{l-1} \bmod Msr modM=sl−1 modM。因此问题转化为：在所有前缀和模 MMM 的结果中，有多少对下标满足模值相同。可以一边计算前缀和，一边统计每种模值出现的次数。每当当前模值为
kkk，就可以和之前所有同样模值的前缀组成合法区间，直接把对应的计数加到答案中。需要注意数组中可能有负数，取模时要调整为非负。整体只需一次线性扫描，时间复杂度是 O(n+M)O(n+M)O(n+M)。
参考代码
T5 午枫的涂色游戏
题目大意
有一排 nnn 个格子，每个格子有初始颜色价值 cic_ici 。小午可以把前 lll 个格子全部涂成价值为 xxx，小枫可以把后 rrr 个格子全部涂成价值为 yyy，且小枫后涂会覆盖小午。两人可以任选 l,rl,rl,r，问最终所有格子的颜色价值总和最小是多少。
题解思路
因为小午只影响前缀，小枫只影响后缀，最终的状态一定是：前面一段被小午涂成 xxx，中间一段保持原样，后面一段被小枫涂成 yyy，并且如果两段有重叠，重叠部分全部算作 yyy。可以先算出原数组的前缀和 sis_isi 。考虑只让小午行动，枚举他涂前 iii 个格子时的总和，即 i⋅x+(sn−si)i \cdot x + (s_n - s_i)i⋅x+(sn −si )，并维护前 iii 的最小值，记为 lil_ili ，表示“小午最多涂到 iii 为止时，能得到的最小总和”。接下来再枚举小枫从右往左涂色，假设她从位置 iii 开始往右全部涂成 yyy，那么中间原本的贡献需要扣掉，再加上
(n−i+1)⋅y(n-i+1)\cdot y(n−i+1)⋅y，此时左侧最优情况就是 li−1l_{i-1}li−1 。把所有这些情况取最小值即可。整个过程只需要前后各扫一遍，时间复杂度是 O(n)O(n)O(n)。
参考代码
T6 午枫的排列
题目大意
给定 1∼n1\sim n1∼n 的一个排列，并给出若干个限制条件，要求在排列中每个 aia_iai 都必须出现在对应的 bib_ibi 之前。在所有满足条件的排列中，输出字典序最小的一个；如果不存在满足条件的排列，则输出 -1。
题解思路
每个限制关系“aia_iai 在 bib_ibi 之前”都可以看成一条从 aia_iai 指向 bib_ibi 的有向边，这样所有限制就构成了一张有向图。题目要求的排列本质上就是这张图的一个拓扑序。如果图中存在环，那么无论如何都无法满足所有限制，直接输出 -1。如果图是有向无环图，那么就可以进行拓扑排序。为了得到字典序最小的拓扑序，在排序过程中，每一步都从当前所有入度为 000 的点中选择编号最小的那个加入结果即可。实现时先统计每个点的入度，用一个小根堆维护当前入度为 000 的点集合，不断取出最小值并更新其后继节点的入度。最终如果能取出恰好 nnn 个点，就得到了答案，否则说明图中存在环。
参考代码
