简介：这份资料是“科大国创杯”2023年安徽省青少年信息学科普日活动ACSP-J组的赛题解析文档，面向备战信息学竞赛的初中生及算法入门学习者，聚焦模拟、排序、双指针、最短路径与区间合并等常见竞赛考点。压缩包内共1个PDF文件，约106KB，以题解正文形式呈现四道题目的思路与复杂度分析：评分题讲解去极值求平均的模拟做法，数数题借助排序与双指针统计合法三角形，行走题在网格图上处理删边后的最短路，石子题则用贪心与栈维护区间合并代价。内容按题目分页组织，每道题均给出算法要点和时间复杂度推导，便于对照练习与复盘。目前已有1315人学习，适合需要梳理竞赛解题框架、查漏补缺的选手参考。
1. 四道题背后的算法直觉：为什么模拟题反而最容易翻车
信息学竞赛里有个反直觉的现象：四道题里，看起来最“送分”的模拟题，往往是全场失分最集中的地方。评分这道题，题意简单到一句话就能说完——去掉最大最小分再求平均，可真正写起来，边界处理、精度控制、排序开销，处处是坑。而数数、行走、石子这三道题，表面考的是双指针、最短路、贪心合并，底层考的其实是同一件事：你能不能把问题的结构看清楚，把暴力枚举的复杂度压下来。这套 ACSP-J 组的题目，恰好把“模拟—排序双指针—图论分层—贪心栈合并”这条从入门到进阶的思维链条完整串了一遍。搞懂这四道题为什么这么设计、每一步复杂度是怎么抠出来的，比刷十道同类题更有价值。
2. 评分与数数：排序之后，暴力枚举怎么被压成线性
2.1 评分题：为什么“只算和”就能省掉一次除法
评分题的题意是：n 个选手，每个选手有 m 个评委打分，去掉一个最高分和一个最低分，求剩余得分的平均值。最直白的写法是每个选手存一个数组，排序，去掉首尾，求和除以 m-2。这个写法没错，但它的复杂度是 O(n·m log m)，排序开销全花在找最大最小值上。
关键观察在于：找最大值和最小值根本不需要完整排序。一次线性扫描就能同时拿到 max 和 min，求和也可以在同一个循环里完成。于是每个选手的处理变成 O(m)，整体 O(n·m)。题目正文里提到“由于评委个数一样，所以可以只算出分数和”，这句话的潜台词是：平均值之间的比较可以转化为总和之间的比较，如果题目只要求排名而不要求输出具体平均分，连除法都能省掉。
常见的实现思路是这样：
def score(players, m): result = [] for scores in players: total = sum(scores) # 一次扫描拿最大最小，避免 O(m log m) 排序 mx = max(scores) mn = min(scores) # 去掉一个最高一个最低，剩余 m-2 个 avg = (total - mx - mn) / (m - 2) result.append(avg) return result这里有个容易被忽略的细节：max和min各扫一遍，加上sum一共三遍，虽然还是 O(m)，但常数是 3。如果追求极致，可以合并成一个循环同时维护 total、mx、mn，常数降到 1。竞赛里 m 通常不大，这点常数差异不影响通过，但“能不能在一个循环里做完”是区分熟练度和直觉的地方。
提示：如果 m 恰好等于 2，去掉最大最小后剩余 0 个评委，除法会除零。题目一般保证 m ≥ 3，但自己写测试时最好覆盖这个边界。
2.2 数数题：双指针的右端点为什么单调
数数题给 n 根木棍，问有多少组三元组 (i, j, k) 满足 i < j < k 且能构成三角形。三角形条件是任意两边之和大于第三边，排序后只需检查最短两边之和大于最长边，即 a[i] + a[j] > a[k]。
暴力三重循环是 O(n³)，n 稍大就超时。排序后，固定 i 和 j，合法的 k 满足 a[k] < a[i] + a[j] 且 k > j。由于数组有序，所有满足 a[k] < a[i] + a[j] 的 k 构成一个从 j+1 开始的连续区间，右端点就是最后一个满足不等式的下标。
核心在于：当 i 固定、j 增大时，a[i] + a[j] 单调不减，所以右端点只会往右移，不会回退。这就是双指针成立的条件——右端点关于 j 单调。于是内层不用每次从 j+1 重新找右端点，而是维护一个指针 k，j 每增大一步，k 就尝试往右扩展。
def count_triangles(a): a.sort() n = len(a) ans = 0 for i in range(n - 2): k = i + 2 # k 至少比 j 大 1，j 从 i+1 开始 for j in range(i + 1, n - 1): if k <= j: k = j + 1 # 右端点单调右移，k 不回退 while k < n and a[i] + a[j] > a[k]: k += 1 # [j+1, k-1] 都是合法的最长边 ans += k - j - 1 return ans这段代码里k在外层 i 固定时只增不减，内层 j 循环总共让 k 移动 O(n) 次，所以固定 i 的复杂度是 O(n)，整体 O(n²)。如果每次 j 增大都重新从 j+1 扫到右端点，最坏会退化回 O(n³)。双指针的“血泪经验”就在这里：指针的单调性必须由问题结构保证，不能想当然。
参数说明：a是排序后的木棍长度数组；k是当前最长边的候选右端点（开区间，即 k 本身不合法）；ans累加的是每个 (i, j) 对应的合法 k 个数。注意k <= j的重置逻辑，当 j 追上 k 时必须把 k 推到 j+1，否则区间会算错。
3. 行走：删掉一条边之后，最短路为什么还能 O(1) 查
3.1 网格图的分层结构：x+y 相同的点在同一斜线
行走题给一个 n×n 网格，从 (1,1) 走到 (n,n)，每步只能向下或向右。每次询问删掉一条边，问最短路长度。不删边时最短路长度固定是 2n-2，因为无论怎么走，向下 n-1 步、向右 n-1 步，总步数不变。
关键观察是：把网格按 x+y 的值分层，每条斜线上的点 x+y 相同。任何一条从 (1,1) 到 (n,n) 的路径，必然依次经过 x+y = 2, 3, ..., 2n 的每一层，每层恰好一个点。一条边连接相邻两层，所以路径可以看成在每两层之间选一条边。
如果删除的边不在某条最短路上，答案不变。如果删除的边在最短路上，问题变成：对这条路径上的每条边，找一条替代边，使得绕行代价最小。由于每层只有一个点，替代边只能在相邻两层之间找，而相邻两层之间的边数是 O(n) 量级。
3.2 替代边的枚举：为什么总复杂度是 O(n² + q)
题目正文给出的思路是：先求一条最短路，对路径上的每条边，枚举所有跟它在同一层之间的边来代替它。路径长度是 2n-2，每条边所在层间的候选边数是 O(n)，所以预处理所有“删路径边”的答案是 O(n²)。询问时，如果删的边不在路径上，直接输出 2n-2；如果在路径上，查预处理结果。总复杂度 O(n² + q)。
这里的设计取舍值得细看：为什么不预处理所有边的删除答案？因为边总数是 O(n²)，每条边都跑一次最短路就是 O(n² · n²)，不可接受。而只预处理路径上的 O(n) 条边，每条花 O(n) 枚举替代，正好 O(n²)。这是典型的“只对可能影响答案的边做预处理”的思路。
def walk(n, removed_edges): # 先求一条最短路，记录路径上的边 path_edges = get_one_shortest_path(n) # 长度 2n-2 path_set = set(path_edges) # 预处理：路径上每条边被删后的最短路 backup = {} for e in path_edges: best = 2 * n - 2 # 枚举与 e 同层的所有边作为替代 for alt in same_layer_edges(e): if alt not in path_set or alt == e: continue # 用替代边绕行的代价 cost = detour_cost(e, alt) best = min(best, cost) backup[e] = best # 回答询问 ans = [] for e in removed_edges: if e not in path_set: ans.append(2 * n - 2) else: ans.append(backup[e]) return anssame_layer_edges(e)返回与边 e 连接相同两层斜线的所有边；detour_cost计算用替代边替换后路径长度的变化。注意替代边本身如果也在路径上，绕行可能形成环，需要排除或特殊处理。这个细节是这道题最容易翻车的地方：替代边不能简单取同层任意边，还要保证替换后路径仍然连通且不重复经过同一层。
注意：如果网格中存在多条最短路，删掉某条路径边后，可能存在另一条完全不经过该层间边的路径。上面的预处理假设替代只发生在同层，这在“路径边被删”时是充分的，因为路径在每层只有一个点，绕行必然发生在该层间。
4. 石子：贪心合并的栈结构，为什么平均值决定顺序
4.1 单点合并：最小值在区间外时为什么要“打包”
石子题先考虑 l = r 的情况：给定一个起点，每次把相邻的两堆合并，花费是两堆石子数之和，问把整个区间合并成一堆的最小花费。这是经典的区间合并问题，但题目正文给出的贪心视角很特别：如果当前未合并部分的最小值就在已合并区间的左边或右边，那一定先合并它。
为什么？因为合并花费与参与合并的堆的大小有关，越小的堆越应该早合并，避免它被后面的大堆“拖累”多次。如果最小值不在已合并区间的紧邻位置，比如最小值在左边但中间隔了几堆，那么中间那些堆合并完之后，下一步必然轮到最小值。于是可以把“最小值及其右侧连续的一段”打包成一个整体，因为它们会紧接着一起被合并。
打包之后，每个包有一个“平均代价”，比较两个包谁先合并，等价于比较它们内部石子的平均值。平均值小的包先合并更优。这个结论的直觉是：先合并的包会被后续每次合并“带上”一次，所以它的单位代价应该更小。
4.2 栈的单调性：从左往右扫，维护平均值递增
对于起点左边的点，从左往右扫，维护一个栈。每次加入一个新点，如果栈顶的平均值大于栈顶下一个的平均值，就把栈顶和栈顶下一个合并。这样栈内从栈顶到栈底平均值递增。右边从右往左同理。询问时，每次选左右栈顶平均值较小的那个合并。
def merge_cost(left_stack, right_stack): cost = 0 while left_stack or right_stack: # 选平均值较小的栈顶先合并 if not right_stack or (left_stack and left_stack[-1].avg <= right_stack[-1].avg): pack = left_stack.pop() else: pack = right_stack.pop() # 合并代价 = 包内石子数 × 已合并区间和 + 包内贡献 cost += pack.size * current_sum + pack.internal current_sum += pack.total return costpack.avg是包内石子的平均值，pack.size是包内堆数，pack.internal是包内合并的内部花费，pack.total是包内石子总数。栈的维护保证了每次取出的都是当前全局最优的合并对象。
题目正文提到“数据随机时栈大小是 O(log n)”，所以对每个位置记录左右栈，总空间 O(n log n)。如果数据不随机，栈可能退化到 O(n)，需要额外维护结构，但这不是考察重点。这里的取舍很清楚：随机数据下，栈的期望深度很小，直接存下来最省事；非随机数据需要更复杂的平衡结构，但竞赛题通常不会在这上面卡人。
提示：栈合并的条件是“栈顶平均值大于栈顶下一个的平均值”，注意是严格大于。如果相等，合不合并都不影响最优性，但会影响栈的大小，实现时统一用大于即可。
5. 避坑与排查：这四道题最容易翻车的五个地方
现象一：评分题用排序找最大最小，大数据超时。原因是对每个选手都做 O(m log m) 排序，n 和 m 都大时常数爆炸。解决方式是改用一次线性扫描同时求 total、max、min，把每个选手的处理压到 O(m)。
现象二：数数题双指针右端点回退，复杂度退化。现象是本地小数据能过，大数据 TLE。原因是内层 j 增大时重新从 j+1 找右端点，没有利用单调性。解决方式是把 k 提到外层，固定 i 时 k 只增不减，j 增大时只做while扩展，不回退。
现象三：行走题替代边选错，答案偏大。现象是删路径边后输出的最短路比真实值大。原因是替代边选在了错误的层间，或者替代边本身也在路径上导致绕行不合法。解决方式是严格按 x+y 分层，替代边必须连接与被删边相同的两层，且替换后路径在每层仍只有一个点。
现象四：石子题栈合并条件写反，贪心失效。现象是合并花费比预期大。原因是把“栈顶平均值大于栈顶下一个”写成了小于，导致栈的单调性方向反了。解决方式是画一个小例子手动模拟，确认平均值小的包应该靠近栈顶（先被合并）。
现象五：边界情况漏判，小数据 WA。评分题 m=2 除零、数数题 n<3 无解、行走题 n=1 路径为空、石子题 l=r 单点。这些边界在样例里往往不出现，但评测数据一定会覆盖。养成习惯：写完先手造最小规模输入跑一遍。
6. 从 O(n³) 到 O(n²)：复杂度压缩的通用直觉
这四道题放在一起看，其实在反复训练同一种能力：识别问题结构，找到单调性或不变量，把暴力枚举的维度降下来。评分题的不变量是“总和减去最大最小”，数数题的单调性是“右端点随 j 增大而右移”，行走题的结构是“按 x+y 分层后每层一个点”，石子题的贪心依据是“平均值小的包先合并”。
我一般会这么理解复杂度压缩：先写出最暴力的解法，然后问自己——枚举的哪些维度是冗余的？哪些量在枚举过程中单调变化？哪些子问题被重复计算了？数数题里，固定 i 后 j 和 k 的关系是单调的，所以 k 不用每次重找；行走题里，路径边只有 O(n) 条，所以只对它们预处理；石子题里，栈的单调性让每次合并的选择变成 O(1)。
一个可验证的检查方法是：写完代码后，构造一组让指针“最坏移动”的数据，数一数内层循环实际执行了多少次。如果次数和理论复杂度对不上，说明单调性没利用好。比如数数题，如果 k 在 j 循环里被重置，实际执行次数就是 O(n³)，一测便知。
| 题目 | 暴力复杂度 | 压缩后 | 关键结构 |
|---|---|---|---|
| 评分 | O(n·m log m) | O(n·m) | 线性扫描替代排序 |
| 数数 | O(n³) | O(n²) | 右端点单调 |
| 行走 | O(q·n²) | O(n²+q) | 按斜线分层，只预处理路径边 |
| 石子 | O(n²) 单点 | O(n log n) | 平均值单调栈 |
从那以后我每次遇到“看起来能暴力”的题，都会先强制自己写出暴力版，再逐条问“这个循环能不能不跑”。希望这套题的结构分析，能帮你在下一次比赛里少踩一个坑。
本文还有配套的精品资源，点击获取
