赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平。
题目编号 题目名称 题目难度 T1 星灯焦点 入门 T2 展厅排期 普及- T3 能量搭档 普及- T4 同步钟声 普及- T5 传送门迷宫 普及- T6 星愿密码 普及/提高-
T1 星灯焦点
题目大意
给出一个 n×mn\times mn×m 的数字矩阵，如果一个位置的数字同时等于所在行最大值和所在列最大值，则称为焦点灯。
求焦点灯数量。
题解思路
先预处理每一行和每一列的最大值。
使用 row[i] 保存第 iii 行最大值，使用 col[j] 保存第 jjj 列最大值。
再次遍历矩阵，如果：
ai,j=row[i]a_{i,j}=row[i] ai,j =row[i]
并且：
ai,j=col[j]a_{i,j}=col[j] ai,j =col[j]
则该位置满足条件。
参考代码
T2 展厅排期
题目大意
给出多个活动的开始时间和持续时间，活动之间需要留出整理时间，求最多安排多少活动。
题解思路
将每个活动转换为区间：
[si,si+di−1][s_i,s_i+d_i-1] [si ,si +di −1]
按照结束时间从小到大排序。
每次选择当前能够安排且结束时间最早的活动。
如果：
si≥last+c***_i\ge last+c****i ≥last+c+1
则选择该活动。
这是经典区间调度贪心问题。
参考代码
T3 能量搭档
题目大意
选择两名同学组成队伍，使两人的能量和满足：
L≤ai+aj≤RL\le a_i+a_j\le R L≤ai +aj ≤R
求最多队伍数量。
题解思路
先排序，然后使用双指针。
如果当前最小值和最大值之和小于 LLL，移动左指针。
如果大于 RRR，移动右指针。
如果满足条件，则组成一队，两个指针同时移动。
参考代码
T4 同步钟声
题目大意
两个钟分别每隔 aaa 和 bbb 分钟响一次，求第 kkk 个响铃时间。
题解思路
设时间为 xxx，计算前 xxx 个时间中响铃次数：
count(x)=⌊xa⌋+⌊xb⌋−⌊xlcm(a,b)⌋count(x)= \lfloor\frac{x}{a}\rfloor+ \lfloor\frac{x}{b}\rfloor- \lfloor\frac{x}{lcm(a,b)}\rfloor count(x)=⌊ax ⌋+⌊bx ⌋−⌊lcm(a,b)x ⌋
寻找最小的 xxx 满足：
count(x)≥kcount(x)\ge k count(x)≥k
由于函数单调，因此使用二分答案。
参考代码
T5 传送门迷宫
题目大意
迷宫中存在传送门，相同字母的位置可以一步传送，求起点到终点最短距离。
题解思路
所有移动代价均为 111，因此使用 BFS。
普通移动扩展四个方向。
对于传送门，每种字母只需要展开一次：
* 第一次遇到某字母时，将所有对应位置加入队列。
* 后续不再重复展开。
避免重复计算。
参考代码
T6 星愿密码
题目大意
字符串中包含数字和 ?，问号可以替换成任意数字。
求所有合法解码方案数量。
题解思路
使用动态规划。
设：
dp[i]dp[i] dp[i]
表示前 iii 个字符的方案数。
当前位置有两种转移：
单个字符：
dp[i]+=dp[i−1]×one(i)dp[i]+=dp[i-1]\times one(i) dp[i]+=dp[i−1]×one(i)
两个字符：
dp[i]+=dp[i−2]×two(i−1,i)dp[i]+=dp[i-2]\times two(i-1,i) dp[i]+=dp[i−2]×two(i−1,i)
其中需要计算问号情况下的组合数量。
每个位置只处理一次。
参考代码
