初等算法与贪心思维
如果说第一赛段考查的是基础编程语法,第二赛段则直接进入算法决策的核心。本模块将重点破解枚举剪枝的临界判断、物理步长模拟以及经典贪心策略的正确性证明。
2.2 枚举搜索与剪枝优化(Pruning)
枚举是计算机最强大的基本能力,但暴力盲目的枚举会导致时间复杂度爆炸。剪枝(Pruning)就是在搜索树生长过程中,利用数学条件提前判断某一分支绝不可能产生合法解,从而“咔嚓”剪掉整条子树。
常见剪枝策略 1:奇偶性剪枝
在数轴移动或网格走步中,若当前点到目标点的曼哈顿距离与剩余可用步数的奇偶性不一致,则绝对无法到达!无需继续向下枚举。
// 若两点差值与步数奇偶不同,立即剪枝
if ((abs(target - current) % 2) != (remainSteps % 2)) return;
常见剪枝策略 2:上下界边界剪枝
若已枚举部分的累加和加上后续所有可能的最大上限,依然达不到目标值;或者当前累加已经超过目标限制,直接退出循环。
// 超出阈值提前 break
if (currentSum + minPossibleRest > target) break;
2.3 物理与博弈过程模拟(2025 真题深度剖析)
模拟题要求选手严格遵循题干给出的物理规则或游戏流程,在草稿纸上建立状态转移方程,并推导出潜在的数学周期或极值规律。
递增步长数轴跳跃模拟
题意:起点在数轴 0 点。第 1 步跳 1 单位,第 2 步跳 2 单位……第 k 步跳 k 单位。每次可选择向左或向右跳。陶陶要到 56,乐乐要到 61,分别最少跳几次?
若把其中某一步(例如第 i 步)改为向左跳,总位移就会从
+ i 变成 - i,总和减少了 2i(减少量永远是偶数!)。因此,能否到达目标 target 的充要条件是:
1. S(k) ≥ target;
2. (S(k) - target) 必须是偶数!
• k = 11:S(11) = 66 ≥ 56。差值 = 66 - 56 = 10(偶数!只需把第 5 步向右改为向左,总和恰好是 56)。
• 因此陶陶最少跳 11 次!
• k = 12:S(12) = 78。差值 = 78 - 61 = 17(奇数,不可行);
• k = 13:S(13) = 91。差值 = 91 - 61 = 30(偶数!可行!只需把第 15 步……或者两步组合调头)。
• 因此乐乐最少跳 13 次!
2.4 贪心算法与区间调度(Greedy Strategy)
贪心算法在每一步决策时,都做出在当前看来最好的选择,而不从整体最优考虑。贪心能够得到全局最优解的前提是问题具有贪心选择性质与最优子结构。
🎯 经典对决:活动区间调度问题的 3 种排序策略对比
给定若干个活动,每个活动有开始时间 s_i 和结束时间 f_i,要求互不冲突的前提下安排尽可能多的活动:
| 策略名称 | 排序依据 | 是否最优? | 反例或证明逻辑 |
|---|---|---|---|
| 策略 A | 按开始时间 s_i 从小到大 | ❌ 错误 | 若第一个活动非常长(如 [0, 100]),选了它就会导致后续所有短活动全部无法安排! |
| 策略 B | 按持续时间 f_i - s_i 从短到长 | ❌ 错误 | 若短活动位于中间 [4, 6],而两侧有两个长活动 [1, 5] 和 [5, 9],选短活动只能安排 1 个,选两侧可以安排 2 个! |
| 策略 C | 按结束时间 f_i 从小到大 | ✔ 严格最优 | 优先选择最早结束的活动,为后续所有剩余活动腾出尽可能最大的时间空间!严格数学归纳法可证。 |
2.5 高阶贪心案例:树木砍伐与单调栈删数
平直道路伐木工人贪心
10 棵树坐标为 7, 10, 12, 15, 19, 20, 53, 63, 75, 87,高度分别为 12, 2, 2, 1, 2, 1, 25, 10, 12, 1。树只能向左倒或向右倒,区间不能有其他树或被占据点。
1. 第 1 棵树:毫不犹豫向左倒(左边无限空地),必能砍伐;
2. 中间各树:优先向左倒(向左倒绝不会占用右边的潜在空地);若左边被挡,尝试向右倒并记录右边界;若右边也被挡,则保持站立不砍;
3. 最后一棵树:毫不犹豫向右倒(右边无限空地),必能砍伐;
经逐棵推演,10 棵树中只有第 6 棵受阻,最多能砍伐 9 棵!
单调栈贪心删数求最大多位数
将 1 到 30 拼接成一个 51 位的大数:123456789101112...282930。从中删去 45 个数字,剩下 6 位数字组成的新数最大是多少?
• 高位权重远大于低位权重!第一目标是让最高位尽量是 9;
• 删去 1~8 共 8 个数字,让首位拿到 9;
• 在 "19" 处再删去前面的数字,让第二位再拿到 9;
• 在删数配额 45 的紧约束下,通过单调栈严格计算,最终留下的 6 位数为:998930!
模块二 · 全真过关检测(共5题)
优先安排最早结束的活动可以为后续腾出最多的可用时间窗口,故按结束时间 f_i 升序贪心能够严格达到全局最优。故选 B。
第 1 棵向左倒,最后一棵向右倒;中间各棵优先向左、次优先向右贪心判定,经序列逐一检测,仅第 6 棵树(坐标 20)左右均受阻,最多可砍伐 9 棵。故选 C。
前 k 步和 S = k(k+1)/2 ≥ target 且差值为偶数。
• 对 56:k=11 时 S=66,差 10 为偶数,最少 11 步;
• 对 61:k=13 时 S=91,差 30 为偶数,最少 13 步。故选 D。
环形图论模拟中,合法环状态等价于每个连续交替方向成对匹配。通过环形动态规划比对,目标串与合法串的最小汉明距离为 3。最少需要 3 次修改。故选 C。
1 到 30 拼接总长 51 位,删去 45 位保留 6 位数。应用单调递减栈贪心,高位尽可能留 9,在删数额度耗尽前保留的前三位为 9、9、8,后三位为 9、3、0,拼出最大数为 998930。故选 B。