赛纲介绍
本次题目的参考难度如下，各位选手可以借此评估一下自身的技术水平。
题目编号 题目名称 题目难度 T1 星码校验 入门 T2 星光增幅 普及- T3 星石叠合 普及- T4 星港连桥 普及/提高- T5 风向通道 普及/提高- T6 星愿配对 普及/提高-
T1 星码校验
题目大意
给出 nnn 个编号，分别计算每个编号从左到右的奇数位数字和、偶数位数字和。如果两者差值的绝对值不超过 kkk，则该编号为稳定星码。求稳定星码的数量。
题解思路
将编号作为字符串读入，依次遍历每一位，将字符减去 '0' 得到对应数字，再按位置分别累加。
需要注意，字符数组的下标从 000 开始，所以偶数下标对应题目中的奇数位，奇数下标对应题目中的偶数位。
每处理完一个编号，判断 abs(odd-even)<=k 是否成立，成立则答案加一。
参考代码
T2 星光增幅
题目大意
nnn 盏灯的初始亮度都是 000。进行 mmm 次区间增幅，每次将 [l,r][l,r][l,r] 中所有灯的亮度增加 www。求最终的最高亮度，以及达到最高亮度的灯的数量。
题解思路
如果每次都遍历整个区间修改亮度，最坏需要 O(nm)O(nm)O(nm) 的时间。由于只询问所有操作完成后的结果，可以使用差分数组。
设差分数组为 d。将区间 [l,r][l,r][l,r] 全部增加 www，只需要修改两个位置：
d[l]=d[l]+w,d[r+1]=d[r+1]−wd[l]=d[l]+w,\qquad d[r+1]=d[r+1]-w d[l]=d[l]+w,d[r+1]=d[r+1]−w
所有操作结束后，从左到右求差分数组的前缀和，就能得到每盏灯的最终亮度。
用 now 记录当前亮度，mx 记录最高亮度，cnt 记录出现次数。如果 now>mx，更新最高亮度并将次数设为 111；如果 now==mx，将次数加一。
差分数组需要能够访问第 n+1n+1n+1 个位置，但统计答案时只遍历 1∼n1\sim n1∼n。亮度最高可能达到 2×10142\times 10^{14}2×1014，差分值和累计亮度都需要使用 long long。
参考代码
T3 星石叠合
题目大意
从左到右依次放入星石。如果最右端两块星石的数字相同，就将它们合成一块数字加 111 的星石，并继续检查能否合成。求最终剩余星石的数量及从左到右的数字。
题解思路
每次合成都只会发生在最右端，可以使用栈维护当前剩余的星石。
用数组 st 模拟栈，top 表示栈内元素数量。每次将新数字放入栈顶，再检查栈顶两个数字是否相同。
如果相同，就令 st[top-1]++，再将 top 减一，表示两块星石合成一块。合成后的星石可能继续与前一块合成，所以这里需要使用 while 循环。
所有数字处理完后，top 就是剩余数量，st[1] 到 st[top] 就是从左到右的结果。
虽然有两层循环，但每次合成都使星石数量减少 111，总合成次数不超过 n−1n-1n−1。
参考代码
T4 星港连桥
题目大意
给出 nnn 个星港和 mmm 条候选桥梁，每条桥梁连接两个星港并有对应费用。选择一些桥梁使所有星港连通，求最小总费用；如果无法连通，则输出 −1-1−1。
题解思路
将星港看作点，桥梁看作无向边，建造费用看作边权。本题就是求无向图的最小生成树，可以使用 Kruskal 算法。
将所有边按费用从小到大排序，依次考虑是否选择。使用并查集维护当前已经连通的星港：
* 如果一条边的两个端点已经在同一个集合中，加入它会形成环，不需要选择。
* 如果两个端点位于不同集合，就选择这条边，累加费用，并合并两个集合。
每次选择的都是连接不同连通块的最便宜的边。如果某个最优方案没有这条边，加入它后可以在形成的环中，替换掉一条跨越这两个部分且费用不更低的边，总费用不会增加。因此按这个顺序选择能够得到最小生成树。
用 cnt 记录选择的边数。最后如果 cnt==n-1，说明所有星港已经连通，否则输出 −1-1−1。当 n=1n=1n=1 时，不需要建桥，答案为 000。
参考代码使用路径压缩，并将较小的集合合并到较大的集合中，sz 记录集合大小。总费用需要使用 long long。
参考代码
T5 风向通道
题目大意
每个格子有一个方向，可以向上下左右相邻格移动。如果移动方向与出发格子的方向相同，代价为 000；否则代价为 111。求起点到终点的最小总代价。
题解思路
将每个格子看作一个点，相邻格子之间的移动看作有向边。边权只可能是 000 或 111，可以使用 0-1 BFS。
用 dis[x][y] 记录到达格子 (x,y)(x,y)(x,y) 的最小能量。初始时将所有距离设为无穷大，起点距离设为 000，放入双端队列。
每次取出队首，检查四个方向。设移动到相邻格的代价为 www，如果：
dis[x][y]+w<dis[nx][ny]dis[x][y]+w<dis[nx][ny] dis[x][y]+w<dis[nx][ny]
就更新相邻格的距离，并根据代价决定入队位置：
* w=0w=0w=0 时，放到队首；
* w=1w=1w=1 时，放到队尾。
这样能够优先处理距离较小的位置：零代价移动仍在当前距离层，一代价移动进入下一层。格子第一次从队首取出并处理时，最短距离已经确定，可以用 vis 标记，跳过之后重复取出的记录。
需要注意，代价由出发格子 g[x][y] 决定；也不能在第一次入队时就把格子标记为已确定，因为之后仍可能找到代价更小的路径。
参考代码
T6 星愿配对
题目大意
将 nnn 块星愿石全部两两配对，每块石头恰好使用一次。第 iii 块和第 jjj 块配对得到 ci,jc_{i,j}ci,j 点星愿值，求最大总星愿值。
题解思路
nnn 不超过 202020，可以用一个整数的二进制位表示哪些石头已经参与配对，进行状态压缩动态规划。
用状态 sss 的第 i−1i-1i−1 位表示第 iii 块石头是否已经使用：这一位为 111 表示已使用，为 000 表示未使用。
dp[s] 记录按下面的顺序配对、到达状态 sss 时能够获得的最大星愿值。初始时 dp[0]=0，其余状态设为 −1-1−1，表示尚未到达。题目保证星愿值非负，因此可以用 −1-1−1 区分不可达状态。
对于每个可达且尚未配完的状态，先找到编号最小的未使用石头 iii，再枚举另一块未使用的石头 jjj，将它们配成一对。
只需要枚举 j>ij>ij>i，因为编号小于 iii 的石头已经全部使用。令新状态为：
t=s ∣ (1<<(i−1)) ∣ (1<<(j−1))t=s\;|\;(1<<(i-1))\;|\;(1<<(j-1)) t=s∣(1<<(i−1))∣(1<<(j−1))
这里的 | 是按位或运算，将对应的两个二进制位设为 111。转移为：
dp[t]=max(dp[t],dp[s]+ci,j)dp[t]=\max(dp[t],dp[s]+c_{i,j}) dp[t]=max(dp[t],dp[s]+ci,j )
固定最小的未使用编号不会漏掉最优配对：对于任意一种完整配对方案，都可以先处理包含这块石头的一对，再用相同规则处理剩余石头。配对的先后顺序不会改变总星愿值。
每次转移都会将两个原本为 000 的位置变为 111，所以 t>st>st>s，从小到大枚举状态即可。全部石头都使用时，状态为 2n−12^n-12n−1，答案就是 dp[(1<<n)-1]。
最多枚举 2n2^n2n 个状态，每个状态用 O(n)O(n)O(n) 的时间寻找石头和枚举搭档，总时间复杂度为 O(n2n)O(n2^n)O(n2n)，空间复杂度为 O(2n+n2)O(2^n+n^2)O(2n+n2)。总星愿值可能达到 101010^{10}1010，需要使用 long long。
参考代码
