挑战赛#34思路
2026-08-02 17:25:48
发布于：上海
1.星灯焦点
思路
先读入 n、m 和整个矩阵；
预处理 row_max[i]：第 i 行的最大值；
预处理 col_max[j]：第 j 列的最大值；
遍历矩阵每一个元素 a[i][j]：
如果 a[i][j] == row_max[i] && a[i][j] == col_max[j]，计数 + 1；
输出计数结果。
复杂度：(O(nm))，n,m≤1000，总元素最多 1e6，完全满足时间限制。
2.展厅排期
思路：贪心，按活动结束时间升序排序，优先选结束早的活动。
数据 (n\le 2\times 10^5)，使用快速 IO。
3.能量搭档
题意分析给定数组，两两配对，要求两人和满足 (L \le a_i+a_j \le R)，每个人最多一组，求最多配对数量。
(n \le 2\times 10^5)，只能 (O(n\log n)) 算法。正确思路（贪心 + 双指针）先排序数组。
最大化配对的经典策略：双指针两头匹配
左指针 l 在最左，右指针 r 在最右：
如果 (a[l]+a[r] \in [L,R])：可以配对，答案 + 1，l++ , r--
如果 (a[l]+a[r] < L)：和太小，左边太小，l++
如果 (a[l]+a[r] > R)：和太大，右边太大，r--
证明：该贪心策略可以得到最大配对数（区间配对最大化标准解法）
4.同步钟声
思路分析题目：求第 k 个能被 a 或者 b 整除的正整数（公倍数只算一次）数学公式（容斥原理）设 (f(x)) = 1~x 内至少一座钟响起的时刻数量：
(f(x)=\left\lfloor \frac{x}{a} \right\rfloor + \left\lfloor \frac{x}{b} \right\rfloor - \left\lfloor \frac{x}{lcm(a,b)} \right\rfloor)
(lcm(a,b)) 最小公倍数，(lcm(a,b)=\dfrac{a}{gcd(a,b)} \times b)（先除后乘，防止溢出）算法：二分答案寻找最小的 x，满足 (f(x) \ge k)，这个 x 就是答案。
下界：1
上界：(k \times \min(a,b))（保证一定存在 k 个满足条件的数）
T ≤ 1e4，每组二分约 60 次，总运算量很小。
5.传送门迷宫
题意要点
上下左右移动：1 步；
当前格子是小写字母c，可以花费 1 步传送到任意另一个相同字母 c的格子；
BFS 求最短路（无权图最短路标准算法）；
优化关键点：同一个字母的传送门只需要展开一次！
如果多次展开同一个字母，会大量重复入队，导致超时。
开数组标记字母是否已经用过，一旦展开，后续遇到同字母不再传送。
思路
预处理：遍历地图，记录每个小写字母 (a~z) 所有坐标，同时找到起点 S 坐标；
BFS 队列保存 (x,y,step)；vis 二维数组标记格子是否访问；
出队一个格子：
如果是终点 T，直接输出步数；
先处理四个方向正常移动；
如果当前格子是小写字母，且该字母没被展开过：
遍历这个字母所有坐标，没访问过就入队（step+1），然后标记该字母已使用；
队列为空说明无法到达，输出 - 1。
6.星愿密码
题意梳理字符串由数字、?组成，?可替换为 0~9 任意数字。
编码规则：
单个字符：只能是 1~9 有效；0 不能单独编码。
相邻两个字符合并：构成数字 10~26 有效。
整串必须完整分割，不同问号替换方案 + 不同分割方案都算不同方案。
求总方案数，对 (MOD=10^9+7) 取模。
(n \le 2\times10^5)，必须线性 DP，用滚动数组优化空间。
DP 定义设 (dp[i])：前 i 个字符合法方案总数。
边界：(dp[0]=1)（空串有一种方案）。
转移：
(dp[i] = A \cdot dp[i-1] + B \cdot dp[i-2])
A：第 i 位单独编码的可选数字数量（满足 1~9）
B：第 (i-1,i) 两位合并编码的可选数字组合数量（满足 10~26）
计算 A（单字符合法数量）
(s[i-1] == '?')：可选 1~9 → (A=9)
(s[i-1] == '0')：不能单独 → (A=0)
其他数字（1~9）：(A=1)
计算 B（两位组合合法数量，字符位置 i-2 和 i-1）设 c1 = s [i-2], c2 = s [i-1]，统计所有 (x,y) 满足：
(10 \le 10\cdot x + y \le 26)，x,y∈0~9，且符合 c1/c2 的限制（固定数字或任意）。
枚举所有情况计算合法对数：
c1 是数字 d1，c2 是数字 d2：
val = d1*10+d2，满足 10~26 → B=1 否则 0
c1 数字，c2 是 '?'：
求有多少 y，(10d1+y \in [10,26])
c1 是 '?'，c2 数字：
求有多少 x，(10x+d2 \in [10,26])
c1='?',c2='?'：
合法组合：10~26 一共 17 种 → B=17
样例校验 1：输入 1?2 n=3
s = "1?2"
dp [0]=1
i=1：字符 '1'，A=1 → dp [1]=1dp [0]=1
i=2：字符 '?'
A=9；两位 "1?" 合法组合：10~19 → B=10
dp [2] = 9dp[1] +10dp [0] =9+10=19
i=3：字符 '2'
A=1；两位 "?2"，统计 x 满足 10x+2 ∈[10,26] → x=1,2 → B=2
dp [3] = 1dp[2] + 2*dp[1] = 19 + 2 = 21 ✔ 匹配样例 1
样例 2：输入?0 n=2
i=1：字符 '?' → A=9，dp [1]=9
i=2：字符 '0'
A=0（0 不能单独）；两位 "?0"：10,20 两种合法 → B=2
dp [2] = 0dp[1] + 2dp [0] = 2 ✔ 匹配样例 2
加油！麻烦点赞关注。
这里空空如也
有帮助，赞一个