赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平。
题目编号 题目名称 题目难度 T1 彩灯折返 入门 T2 星环巡检 普及- T3 星尘观测窗 普及- T4 星轨校准 普及- T5 隔墙穿行 普及/提高- T6 星塔连线 普及/提高-
T1 彩灯折返
题目大意
机器人从第 ppp 盏灯出发，按照初始方向在 nnn 盏灯之间往返移动。每次操作先点亮当前位置，再移动一格；如果下一格越界，则先掉头再移动。
求 qqq 次操作后每盏灯被点亮的次数。
题解思路
按照题意直接模拟机器人的位置和方向。
使用 dir 表示当前方向：向右时为 111，向左时为 −1-1−1。每次操作先令当前位置的计数加一，再检查 p+dirp+dirp+dir 是否越界。如果越界，就令 dir=-dir，最后移动到 p+dirp+dirp+dir。
当 n=1n=1n=1 时，机器人不会移动，唯一一盏灯会被点亮 qqq 次，对此情况单独处理。
参考代码
T2 星环巡检
题目大意
nnn 个展台围成一圈。机器人从第 ppp 个展台开始，每次先记录当前位置，再顺时针移动 kkk 个展台。
求 qqq 次巡检中记录过多少个不同的展台。
题解思路
将展台编号放在模 nnn 的意义下考虑。机器人记录的位置依次为：
p,p+k,p+2k,⋯(modn)p, p+k, p+2k, \cdots \pmod n p,p+k,p+2k,⋯(modn)
设机器人经过 ttt 次移动后第一次回到起点，则需要满足：
tk≡0(modn)tk\equiv 0\pmod n tk≡0(modn)
最小的正整数 ttt 为：
ngcd(n,k)\frac{n}{\gcd(n,k)} gcd(n,k)n
因此，机器人移动形成的循环中共有 ngcd(n,k)\dfrac{n}{\gcd(n,k)}gcd(n,k)n 个不同展台。如果巡检次数 qqq 小于循环长度，只会记录前 qqq 个不同展台；否则会记录完整个循环。
答案为：
min(q,ngcd(n,k))\min\left(q,\frac{n}{\gcd(n,k)}\right) min(q,gcd(n,k)n )
初始位置 ppp 只影响具体经过哪些展台，不影响不同展台的数量。
参考代码
T3 星尘观测窗
题目大意
给出长度为 nnn 的序列，统计有多少个连续区间 [l,r][l,r][l,r] 满足：
max(al,al+1,⋯ ,ar)−min(al,al+1,⋯ ,ar)≤D\max(a_l,a_{l+1},\cdots,a_r)-\min(a_l,a_{l+1},\cdots,a_r)\le D max(al ,al+1 ,⋯,ar )−min(al ,al+1 ,⋯,ar )≤D
题解思路
使用双指针维护一个满足条件的滑动窗口 [l,r][l,r][l,r]。
从左到右枚举右端点 rrr，将 ara_rar 加入窗口。参考代码使用 map 记录窗口内每个数的出现次数，因此：
* mp.begin()->first 是窗口最小值；
* mp.rbegin()->first 是窗口最大值。
如果最大值与最小值之差大于 DDD，就不断删除左端点对应的元素并右移 lll，直到窗口重新满足条件。
对于固定的右端点 rrr，当 [l,r][l,r][l,r] 满足条件时，它的任意后缀也满足条件。因此，以 rrr 为右端点的合法区间共有：
r−l+1r-l+1 r−l+1
将这个数量累加到答案中即可。答案最多达到 n(n+1)2\dfrac{n(n+1)}22n(n+1) ，需要使用 long long。
每个元素至多进入和离开窗口一次。
参考代码
T4 星轨校准
题目大意
给出 nnn 个信号点的位置。每移动一个信号点 111 个单位会产生 111 的代价。
选择至少 kkk 个信号点，将它们移动到同一个整数位置，求最小总代价。
题解思路
如果一个方案将多于 kkk 个点移动到同一位置，那么只保留其中任意 kkk 个点，代价不会增加。因此只需要考虑恰好选择 kkk 个点。
先将所有位置从小到大排序。最优选择一定可以对应排序数组中一段长度为 kkk 的连续区间：如果选择了区间两侧较远的点，却跳过了中间的点，用中间的点替换较远的点不会使代价变大。
对于一段排好序的数，将所有数移动到中位数时绝对距离之和最小。因此枚举每个长度为 kkk 的区间 [l,r][l,r][l,r]，其中：
r=l+k−1,qquadmid=⌊l+r2⌋r=l+k-1,qquad mid=\left\lfloor\frac{l+r}{2}\right\rfloor r=l+k−1,qquadmid=⌊2l+r ⌋
目标位置取 amida_{mid}amid 。设 pre[i] 为排序后前 iii 个数的前缀和，则左侧所有点移动到中位数的代价为：
amid(mid−l+1)−(pre[mid]−pre[l−1])a_{mid}(mid-l+1)-(pre[mid]-pre[l-1]) amid (mid−l+1)−(pre[mid]−pre[l−1])
右侧所有点移动到中位数的代价为：
(pre[r]−pre[mid])−amid(r−mid)(pre[r]-pre[mid])-a_{mid}(r-mid) (pre[r]−pre[mid])−amid (r−mid)
两部分相加就是当前区间的最小代价，枚举所有区间取最小值即可。kkk 为偶数时，两个中间数之间的任意整数都能取得最小值，参考代码选择左侧中位数，同样正确。
参考代码
T5 隔墙穿行
题目大意
在一个由空地和墙壁组成的迷宫中，从起点走到终点。可以正常走到相邻空地，也可以一步穿过相邻的一堵墙，到达墙另一侧的空地，但不能连续两步穿墙。
求到达终点的最少步数，无法到达则输出 −1-1−1。
题解思路
每次正常移动或穿墙移动的代价都是 111，可以使用 BFS 求最短路。
能否在下一步穿墙，不仅与当前位置有关，还与上一步是否穿墙有关。因此将状态设为：
(x,y,last)(x,y,last) (x,y,last)
其中 last=0 表示上一步不是穿墙，last=1 表示上一步是穿墙。使用 dis[x][y][last] 记录到达该状态的最少步数。
从一个状态出发有两类转移：
1. 如果相邻格是空地，可以正常走到相邻格，新状态的 last=0。
2. 只有当当前状态的 last=0 时才能穿墙。如果相邻格是墙、同方向再前进一格仍在迷宫内且为空地，就可以一步到达墙后的空地，新状态的 last=1。
BFS 第一次到达每个状态时得到的就是最短距离。最终取终点两个状态的较小距离；如果均不可达，则输出 −1-1−1。
状态数不超过 2nm2nm2nm，每个状态只会检查四个方向。
参考代码
T6 星塔连线
题目大意
给出一棵以 111 号节点为根的树，每个节点有一个初始亮度。一次操作可以将某个节点的整棵子树亮度全部加 111 或全部减 111。
求使所有节点亮度变为 000 的最少操作次数。
题解思路
在节点 uuu 上进行的操作只会影响 uuu 及其后代，不会再影响它的父节点。因此可以按照从根到叶子的顺序依次确定每个节点必须进行的操作。
设 effect[u] 表示根到 uuu 的路径上已经确定的所有操作，对 uuu 及其子树产生的累计影响。
对于根节点，为了将亮度 a1a_1a1 变成 000，必须产生净影响：
effect[1]=−a1effect[1]=-a_1 effect[1]=−a1
所需操作次数为 ∣effect[1]∣|effect[1]|∣effect[1]∣。
对于非根节点 uuu，设父节点为 fff。处理 uuu 前，祖先操作已经使它的亮度变为：
au+effect[f]a_u+effect[f] au +effect[f]
为了让 uuu 变成 000，必须在以 uuu 为根的子树上补充净操作量：
need=−(au+effect[f])need=-(a_u+effect[f]) need=−(au +effect[f])
这需要 ∣need∣|need|∣need∣ 次操作，并且：
effect[u]=effect[f]+needeffect[u]=effect[f]+need effect[u]=effect[f]+need
处理完父节点后有 effect[f]=−afeffect[f]=-a_feffect[f]=−af ，因此也可以写成：
need=af−auneed=a_f-a_u need=af −au
所以答案等价于：
∣a1∣+∑u≠1∣au−afa(u)∣|a_1|+\sum_{u\ne 1}|a_u-a_{\mathrm{fa}(u)}| ∣a1 ∣+u=1∑ ∣au −afa(u) ∣
这个选择是被当前节点变为 000 的要求唯一确定的。来自后代的操作无法影响当前节点，所以不可能通过之后的操作减少这部分代价。因此逐层累加 ∣need∣|need|∣need∣ 就能得到最优答案。
参考代码先用栈得到父节点一定先于子节点的遍历顺序，再依次进行上述计算，避免递归层数过深。
每个节点处理一次，每条边遍历常数次。
参考代码
