赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 奇怪的数组 入门 T2 取与得 普及- T3 机器人Ⅰ 普及- T4 下凸子数组 普及/提高- T5 最短路 普及+/提高 T6 机器人 普及+/提高
奇怪的数组
题目大意
现在你存在一种操作，让数组中的两个位置 iii , jjj ,让第 iii 个数 −1-1−1, 第 jjj 个数 +1+1+1。 求最少可以通过多少次操作可以让数组中的每一个数相同。
题解思路
经过一次操作，数组中的数的总和不变，如果数组中的每一个数最终相同，∑i=1naimod n=0\sum^n_{i=1} a_i \mod n =0∑i=1n ai modn=0,因此我们确认这个数是否可行就可以了。最小次数我们只需要考虑比平均值大的数与平均数的差的和是多少。
参考代码
取与得
题目大意
你可以任意删除并且重新排列原数组，让生成的数组的总权值最大。
题解思路
1. 大的数一定放在前面。
2. 在数组后面添加一个数，本质上总权值加上数组前面一段数的和。
因此本题在排序完进行两次前缀和后找到数组中的最大值即可
参考代码
机器人Ⅰ
题目大意
现在机器人有一种移动方式，问机器人从某一个起点到达 lil_ili rir_iri 位置。
题解思路
问题 111 我们现在机器人从 p0p_0p0 开始,走了一圈到达 p1p_1p1 ，那么 p1p_1p1 的位置会在哪里？
我们设白色节点的数目为 ttt ,那么我们可以到达 (p0+t)mod n(p_0 + t) \mod n(p0 +t)modn 位置。因为这次的移动，本质上是相当与 robotrobotrobot 顺时针走了 ttt 步。
问题 222 现在我们机器人最终到达了 lj,rjl_j , r_jlj ,rj ,那么对于 lj和rjl_j 和 r_jlj 和rj 有什么限制?
其中一个节点应该是最后一步走到的，我们设最后一步走的是顺时针，那么 rjr_jrj , 这个点似乎就相当于未生效。 这样我们可以找到这一圈的起始点 p1p_1p1 。
只后，我们可以从 p1p_1p1 开始模拟，机器人是否可以到底 lj,rjl_j, r_jlj ,rj 。
时间复杂度 O(n×mn \times mn×m)
参考代码
下凸子数组
题目大意
现在需要我们生成一个单调递增的数组，并且数组的增量单调不降，数组的首项为1，末尾为 kkk。
题解思路
我们设增量为 did_idi , 问题可以转化为存在多少种不同的数组，使得 ∑i=1pdi=k−1\sum^p_{i=1}{d_i} = k-1∑i=1p di =k−1，问题可以转换为一个完全背包问题。
参考代码
最短路
题目大意
存在 nnn 个节点 ，mmm 次操作，每次操作或者查询两个节点之间的距离，或者删除一个节点，并且删除一个点，并让其邻域的点两两之间连上一条边。
题解思路
题目分析
我们可以将删除操作的本质理解为：对于所有经过该节点的最短路径，其距离长度将减少 111。基于这一观察，可以将问题转化为以下形式：
初始状态下，所有节点的权值均为 111。操作1对应将指定节点的权值修改为 000，而操作2则转化为查询两个节点之间最短路径上权值为 111 的节点数量。
这种转化使得问题可以通过树链剖分技术高效解决。具体而言，我们可以：
1. 建立树链剖分数据结构来维护节点权值
2. 实现单点修改操作（将节点权值从1改为0）
3. 通过路径查询统计两个节点间最短路径上权值为1的节点数量
时间复杂度 O(nlog2nn\log^2 nnlog2n)
参考代码
机器人
题目大意
现在机器人有一种移动方式，问机器人从某一个起点到达 lil_ili rir_iri 位置。
题解思路
思考一 nnn个点, nnn 条边的图是什么图 ？很明显这是一个基环树。这样我们在求解距离的时候似乎可以转换为环上的两点之间的距离，这样通过一系列离线的操作，可以在 O(n)的时间下求出来。
思考二 现在我们从 p0p_0p0 出发， 走到 li,ril_i, r_ili ,ri ,这会有什么性质，
* 首先出去最后一次移动到的位置，其他的位置都产生了相应的影响。这样我们可以找到开始位置 p1p_1p1
* 还有没有其他性质？设最后一步是向右走，那么 lil_ili 位置一定是白色的。最后一步是向左走 rir_iri 的位置一定是黑色。
* li∼p1l_i \sim p_1li ∼p1 这个位置每一个向右的位置相当于一次转向。在pi∼rip_i \sim r_ipi ∼ri 的位置也是类似。那这个有什么性质呢？我们定pip_ipi 有一个初始方向 a0a_0a0 ,结束的方向为 a1a_1a1 ,如果两个方向相反，那么可以说明左区间的右转向和右区间的左转向数目相同。如果两个方向相同，最终向右走，那么左区间的右转向比右区间的左转向多一个，向左走也类似。
参考代码
