ACSP-J 真题解析：模拟、双指针、最短路与贪心栈的实战技巧

简介：这份资源是“科大国创杯”2023年安徽省青少年信息学科普日活动ACSP-J组的赛题解析文档，面向备战算法竞赛的初中生及信息学教练，聚焦提升算法设计与问题求解能力。内容围绕评分、数数、行走、石子四道题展开，逐题给出思路推导与复杂度分析，覆盖模拟、排序、双指针、最短路径、贪心与区间合并等常见考点，适合赛前专项训练与赛后复盘。资源包共1个PDF文件，约106KB，篇幅精炼，按题目分页组织，便于对照题目快速定位解法要点。目前已有1315人学习，读者可从中获得完整的赛题解法框架、复杂度估算方法以及双指针维护区间、网格分层替代边、栈合并区间等具体技巧，用于查漏补缺和强化竞赛思维。

1. 从“评分”这道签到题说起：ACSP-J 到底考什么

很多人第一次接触这套题，会盯着“石子”那道压轴题发怵，结果回头一看，真正拉开差距的其实是前面几道“看着简单”的题。ACSP-J 这类面向初中生的信息学科普活动，考的不是你会不会背模板，而是能不能在有限时间里把模拟、排序、双指针、最短路、贪心合并这几类基础工具用对地方。四道题的分值分布很典型：签到题保底，第二题拼细节，第三题考图论建模，第四题考思维深度。想拿高分，先把“评分”这种送分题做到零失误，再靠“数数”和“行走”稳住中段，最后用“石子”的贪心栈去冲一冲。这套卷子适合已经学过基础语法、正在刷普及组真题的选手，也适合想检验自己“能不能把会的写对”的备考者。

2. 高频考点拆解：四道题背后的算法清单与真题演练

2.1 评分（score）：模拟题里的“去极值求平均”怎么写才不翻车

这道题题意直白得让人放松警惕：每个选手有若干评委打分，去掉一个最高分和一个最低分，剩下的算平均。很多人上来就排序，排完再求和，复杂度 O(nm log m)，虽然能过，但面试官或出题人更想看到你意识到“评委个数固定，只需要总和减去最大最小”。先读入时维护 sum、max、min，最后 (sum - max - min) / (m - 2) 就完事。时间复杂度降到 O(nm)，代码短且不容易错。

n, m = map(int, input().split()) for _ in range(n): scores = list(map(int, input().split())) total = sum(scores) mx = max(scores) mn = min(scores) # 去掉一个最高分和一个最低分，剩下 m-2 个评委 avg = (total - mx - mn) / (m - 2) print(f"{avg:.2f}")

这段代码的关键在total - mx - mn：不要先删元素再求和，那样既慢又容易在列表操作上翻车。参数上注意 m 至少为 3，否则分母为 0，虽然题目一般会保证，但写的时候心里要有这个边界。输出格式按题目要求保留两位小数，别因为格式丢分。这类题面试官最想听的是“你为什么不用排序”，答出“评委数固定，极值只需一次扫描”就到位了。

2.2 数数（count）：排序加双指针，把三角形计数从 O(n³) 压到 O(n²)

第二题是经典的“三根木棍能拼成三角形”计数。暴力枚举 i<j<k 再判断 a[i]+a[j]>a[k]，复杂度 O(n³)，n 稍微大一点就超时。正确做法是先排序，固定较短的两根 i、j，那么最长的 k 必须满足 k>j 且 a[k] < a[i]+a[j]。因为数组有序，合法的 k 是一段连续区间，左端点固定为 j+1，右端点随着 j 增大而单调右移，于是可以用双指针维护右端点。

a = sorted(map(int, input().split())) n = len(a) ans = 0 for i in range(n - 2): k = i + 2 # 最长边的右端点指针，至少比 j 大 1 for j in range(i + 1, n - 1): if k <= j: k = j + 1 # 右端点单调右移，直到不满足三角形不等式 while k < n and a[i] + a[j] > a[k]: k += 1 ans += k - j - 1 print(ans)

这里k在固定 i 后只增不减，所以内层 while 总共最多走 n 步，整体 O(n²)。易错点在于k的初始化和k <= j的修正：当 j 增大时，k 可能落后于 j，必须强制拉到 j+1。另外计数时是k - j - 1，因为合法区间是 [j+1, k-1]。面试时如果被问“为什么双指针不会漏”，答“排序后不等式具有单调性，右端点随 j 增大只右移”即可。

2.3 行走（walk）：删边最短路，先找一条最短路再按斜线替换

第三题是网格图上的删边最短路。题意是每次删一条边，问从 (1,1) 到 (n,n) 只向下或向右走的最短路。关键观察：如果删的边不在某条最短路上，答案不变；如果删的边在最短路上，由于网格图每条路径长度固定为 2n-2，删掉一条边后只需要找一条“替代边”绕过去。把网格按 x+y 分层，每条边连接相邻两层，删掉某条边后，枚举同一层之间的其他边替换即可。

# 核心思路示意：先求一条最短路，记录路径上的边 # 对路径上的每条边，枚举同层替代边，取最小增量 # 时间复杂度 O(n^2 + q)

这段伪代码的重点不是逐行实现，而是理解“分层替换”的建模：网格图里所有从 (1,1) 到 (n,n) 的路径都经过每一层恰好一次，所以删边的影响局限在相邻两层之间。面试官常追问“为什么复杂度是 O(n²+q)”，答“预处理每条路径边被删后的替代代价是 O(n²)，每次询问 O(1) 查表”。易错点是忘记判断删边是否在最短路上，导致对不在路径上的边也去重算，白白超时。

2.4 石子（stone）：贪心合并与单调栈，O(n log n) 的思维题

压轴题“石子”是整套卷子里最考思维的一道。先看 l=r 的简化版：给定一个起点，每次把相邻两堆合并，花费是两堆石子数之和，求最小总花费。贪心结论是：如果当前未合并区间的最小值在已合并区间的左边或右边，一定先合并它；如果最小值不在旁边，就把它和它右边的点“打包”成一个整体，因为它们在最优方案里一定紧接着一起合并。打包后的整体可以按“内部平均值”比较先后，平均值小的先合并更优。于是对起点左边从左往右扫、维护一个单调栈，栈顶平均值大于下一项就合并；右边从右往左同理。每次询问取左右栈顶平均值较小的那个合并。

# 单调栈维护“打包块”，每块记录 (石子总和, 块内点数) # 合并条件：栈顶块的平均值 > 栈中下一块的平均值 # 询问时双指针从左右栈顶取平均更小者合并

这类题面试官最想听的是“你为什么敢打包”：因为最小值旁边的点被合并后，下一步必然轮到最小值，所以它们可以视为一个整体，且整体内部的合并顺序不影响外部比较。易错点在于只比较单点石子数而忽略“块内点数”对花费的放大效应——合并一个含 x 个点的块，花费是 x 乘以对方石子数，所以比较的是平均值而不是总和。数据随机时栈大小 O(log n)，时空 O(n log n)；即使不随机，多维护一点信息也能处理，但考场上优先拿随机分。

3. 易错点与失分点：这四类错误每年都有人踩

3.1 评分题：先删元素再求和，列表操作拖慢还容易越界

错在哪：拿到题就scores.remove(max(scores))、scores.remove(min(scores))，再sum(scores)/len(scores)。为什么错：remove 是 O(m) 操作，且当最大值有重复时只删一个，逻辑上没问题但常数大；更危险的是先排序再切片，边界写错就少算一个评委。怎么答对：读入时同步维护 sum、max、min，最后一步减法搞定，既快又不会碰列表边界。

3.2 数数题：双指针右端点忘记随 j 修正，计数区间算错

错在哪：固定 i 后 k 从 i+2 开始，内层 j 增大时没有检查k <= j，导致 k 落在 j 左边，k - j - 1变成负数。为什么错：右端点指针的单调性只在“合法区间右端”上成立，j 追上 k 时必须强制把 k 拉到 j+1。怎么答对：内层循环开头加一句if k <= j: k = j + 1，计数用k - j - 1，并在草稿上画一个有序数组验证小样例。

3.3 行走题：对不在最短路上的删边也重算，复杂度直接爆炸

错在哪：每次询问都重新跑一遍 BFS 或 DP 求最短路，q 次询问变成 O(qn²)。为什么错：没有利用“删边不在最短路上则答案不变”这个剪枝，把简单情况也当复杂情况处理。怎么答对：先求一条最短路并标记路径边，询问时先判断被删边是否在路径上，不在就直接输出原最短路长度；在路径上再查预处理的替代代价表。

3.4 石子题：比较打包块时用总和而不是平均值，合并顺序反了

错在哪：两个打包块 x、y 比较谁先合并时，直接比石子总和，认为总和小的先合并。为什么错：合并一个含 x 个点的块，花费是 x 乘以对方石子数，块内点数会放大代价，所以正确比较量是“总和/点数”即平均值。怎么答对：栈里每块存 (sum, cnt)，比较sum1/cnt1与sum2/cnt2，用交叉相乘避免浮点误差；合并时花费按cnt * 对方sum累加。

4. 答题节奏与押题思路：从签到到压轴的时间分配表

真正上了考场，四道题的节奏比单独会做更重要。我的习惯是开考先花三分钟通读全卷，确认“评分”是纯模拟、“数数”是排序双指针、“行走”是图论建模、“石子”是贪心栈，然后按下面的时间表推进：

这张表的核心逻辑是“先保底再冲高”：评分和数数必须一次写对，行走拿到“删边不在最短路”的送分部分，石子先写简化版拿部分分。押题方向上，这类普及组卷子每年必考“排序+双指针”和“网格图最短路”，而“贪心+单调栈”是拉开档次的区分题。复习时不要只背代码，要练“看到删边最短路先想分层替换”“看到合并花费先想平均值比较”这两个条件反射。

从那以后我每次带人刷这套题，都强制先手写一遍评分的极值维护和数数的双指针边界，再上机跑对拍——血泪经验是，签到题翻车比压轴题不会更伤士气。希望帮到你。

本文还有配套的精品资源，点击获取