简介：ACSP-J组赛题解析PDF收录了2023年安徽省青少年信息学科普日活动“科大国创杯”初中组竞赛的完整算法题解，面向参赛学生与算法入门者，覆盖模拟、排序、双指针、图论最短路、区间合并等核心知识。资源共1个PDF文件，压缩包仅106KB，内容紧凑，直接给出每道题的题意概括、突破口和复杂度分析。包内包含“评分”“数数”“行走”“石子”四道题目的解题思路，如去除最高最低分计算均值、排序后双指针维护三角形拼接区间、网格图中分类讨论删除边对最短路的影响、以及结合贪心与栈维护合并顺序的O(n log n)做法。已有1313人学习下载，适合赛前快速回顾算法模型、理解正确性证明与时间代价，也便于教师直接摘录讲解。材料不提供源码，但思路推导完整，有助于青少年选手从题目抽象到算法设计建立清晰认知。

1. 四道题、四种典型套路：把 ACSP-J 组题解拆成可复现代码

先说结论：这套题解的价值不在于“告诉你能不能 AC”，而在于把初中组算法竞赛最常见的四种题型——纯模拟、排序双指针、网格最短路、贪心区间合并——放在同一次练习里串起来。四道题读下来你会发现，真正拉开差距的不是灵光一现的思路，而是边界处理和复杂度估算的细致程度。这份拆解按我平时带学生备赛的习惯，逐题讲清楚时间复杂度怎么推、实现顺序怎么排、哪些地方容易翻车，适合正在备赛的初中生、带竞赛班或信息学社团的讲师，也适合拿这组题补算法模板的开发者。

2. 评分模拟与三角形计数：从去极值平均分到 O(n²) 双指针

2.1 score 去掉极值求平均：用去极值总分代替浮点比较

第一题是典型的签到题，但签到题恰恰最容易在细节上吃罚时。题目描述很直接：每个选手有 m 个评委打分，去掉一个最高分、去掉一个最低分，剩下分数求平均，再按平均分排名。第一次看到这题会本能地想到“每人排序后取中间段”，这当然能做，但每处理一个人就要排一次序，复杂度变成 O(nm log m)，n 和 m 到 10^5 级别就非常吃亏。

这题有一个很关键的观察：评委数量 m 对每个选手是固定的。去极值后的“总分”除以同一个 (m-2)，得到的就是平均分。既然所有选手除的是同一个数，那比较平均分和比较去极值总分就是完全等价的。排序阶段完全不需要出现浮点数，只有最后要输出平均分的那个瞬间才除一次。

# score.py：去掉最高最低后按总分排序，排序过程中不出现浮点 n, m = map(int, input().split()) records = [] for idx in range(n): a = list(map(int, input().split())) total = sum(a) - min(a) - max(a) # 先求和，再删极值，避免多次除法 records.append((-total, idx + 1)) # 取负号让列表按总分降序排列 records.sort() print(" ".join(str(idx) for _, idx in records))

这段代码里最核心的是sum(a) - min(a) - max(a)。先算总和，是因为 min 和 max 都可以在一次遍历中拿到，没必要先排序。后面排序用-total为键，m 固定时总分顺序就是平均分顺序。要注意m-2可能为 0：当 m=2 时，去完极值一个分都不剩，题目一般会保证 m≥3，但如果你在改编数据或本地自测，必须对 m≤2 的情况做特判，否则除零就直接运行时错误。

复杂度方面，读入 n 个选手、每个选手 m 个分数，累加和找极值都是 O(m)，所以整体是 O(nm + n log n)，其中 n log n 来自最后排序。实际实现时把输入输出流关闭同步，能省掉不少常数，尤其是分数数量多的时候。

2.2 count 排序加双指针：右端点只往一个方向走

第二题数三角形组合，暴力枚举三个下标是 O(n³)，n 到几千就会卡死。能压缩到 O(n²) 的核心是：先排序，再利用三角形不等式的单调性。

把木棍长度排成 a1 ≤ a2 ≤ … ≤ an。对升序的三元组 a[i]、a[j]、a[k]（i<j<k），要能组成三角形需要同时满足三个条件：a[i]+a[j]>a[k]、a[i]+a[k]>a[j]、a[j]+a[k]>a[i]。但排序之后，后两个不等式是天然成立的，因为 a[k] 已经是三根里最大的，再加上任何一根正数都会大于另一边。所以唯一要盯住的约束只剩 a[i]+a[j]>a[k]。

固定最短的两根 a[i] 和 a[j]，合法 k 的取值是一个连续区间：左端点是 j+1，右端点是满足 a[k]<a[i]+a[j] 的最大位置。当 j 往右挪的时候，a[i]+a[j] 只增不减，所以这个右端点也只会往右移动。用双指针维护它，每个 i 循环内右端点最多从 i+1 走到 n，均摊 O(n)，总复杂度 O(n²)。

# count.py：排序 + 双指针统计能组成三角形的三元组数量 n = int(input()) a = list(map(int, input().split())) a.sort() # 必须先升序，后续单调性全依赖排序 ans = 0 for i in range(n - 2): k = i + 1 # 每个 i 开始时，右端点重置为最小可能值 for j in range(i + 1, n - 1): while k + 1 < n and a[k + 1] < a[i] + a[j]: k += 1 # 右端点只会向右推进，绝不回退 if k > j: ans += k - j # j+1 到 k 之间的每个下标都能作第三边 print(ans)

这里最容易写错的是 k 的初始化。有人会把 k 定义在外层循环之前，导致上一轮 i 留下的右端点污染下一轮结果；也有人把 k 初始化为 i，while 里会把 a[j] 自己也算进合法集合。正确做法是每个 i 循环开始把 k 放到 i+1，这样 j 从 i+1 起步时 k 恰好等于 j，while 检查 a[j+1]，不会误计入 a[j] 本身。

另一个需要注意的点是严格不等号。a[i]+a[j] 等于 a[k] 时，三根木棍恰好共线，不能构成三角形，所以必须用<而不是<=。样例多半会把这种边界塞进去，用等号会多统计出一批非法组合。

2.3 数据范围与输入输出习惯：先看约束再选类型

两道题放在一起说，是因为它们都容易在“数据范围”上翻车。score 的求和是 int 范围内可能没问题，但 count 的答案组合数在 n=10^5 时最坏情况下是 C(n,3)，大约 1.6×10^14，远超 32 位整型。写 C++ 时用long long，写 Python 时不用操心但要注意性能。我一般拿到题第一件事就是看 n、m、q 的上限，在代码开头注释里标出n<=1e5, ans要开long long，省得写完再回头改类型。

输入输出方面，n 和 m 大时不要用endl硬刷缓冲区，C++ 关掉cin.tie(nullptr)，Python 则用sys.stdin.buffer.read()一次性读入再切分。这类竞赛数据量一旦上去，IO 本身就可能吃掉大半时间预算。

3. 删边最短路与石子合并贪心：分层替换与单调栈的两道硬题

3.1 walk：网格 DAG 上的最短路 DP 与前驱记录

walk 这题第一眼像动态规划，仔细一想确实就是动态规划——因为每一步只允许向右或向下，图不存在环，最短路可以在每个点取“上方来的路径”和“左方来的路径”的最小值，转移顺序就是逐行逐列扫描。

# walk.py：网格最短路的 DP 实现，并记录前驱方向 INF = 10**18 dist = [[INF] * (n + 1) for _ in range(n + 1)] dist[1][1] = 0 pre = {} for i in range(1, n + 1): for j in range(1, n + 1): if i == 1 and j == 1: continue # up_w[i][j] 表示从 (i-1,j) 到 (i,j) 的边权 # left_w[i][j] 表示从 (i,j-1) 到 (i,j) 的边权 from_up = dist[i - 1][j] + up_w[i][j] from_left = dist[i][j - 1] + left_w[i][j] if from_up < from_left: dist[i][j] = from_up pre[(i, j)] = (i - 1, j) else: dist[i][j] = from_left pre[(i, j)] = (i, j - 1)

这段代码里的pre字典维护的是“从哪个格子转移过来”。做完 DP 后，从 (n,n) 沿着 pre 一路回溯到 (1,1)，就能拿到一条最短路上的完整边序列。这里边权数组的坐标约定要提前定死：up_w[i][j]存的是进入 (i,j) 的上方边权，left_w[i][j]存的是进入 (i,j) 的左侧边权。下标错一位是最容易犯的错，我习惯在注释里把“边权属于进入点”写清楚。

有了这条最短路，q 次删边查询就不用每次重跑全局 DP。先把最短路上的边放进一个哈希集合，查询时判断删除的边在不在集合里。如果不在，最短路一条边都没被碰，答案直接输出dist[n][n]。真正需要处理的，是恰好删中这条路径上的某一条边。

3.2 斜线分层替换：删边问题变成同层枚举

现在剩下的问题是：如果删除的边恰好在这条最短路上，能不能快速算新的最短路？直接重新跑一遍 DP 需要 O(n²)，q 大一点就超时。题解的做法是按斜线分层。

观察整个网格：所有满足 x+y 相同的点 (x,y) 构成一条斜线，任何一条从 (1,1) 到 (n,n) 的路径，本质上都是按 x+y 逐层前进，每一层用一条边跳到下一层。所以一条最短路可以看成若干条“层间边”的拼接。删除其中一条边，最优替代一定也是连接这两个相邻斜线层的某条边。于是可以提前把每条最短路边的“起点斜线编号 x+y”记下来，查询时枚举同一层之间的所有候选边，挑一条权值最小的去顶替。

# walk_query.py：穷举同层边做替代（示意结构，边权数组按题面定义） shortest_set = set() # 存最短路上的 (x1,y1,x2,y2) for x1, y1, x2, y2, dead_w in deleted_edge: if (x1, y1, x2, y2) not in shortest_set: print(dist[n][n]) # 删的边不在最短路上 continue level = x1 + y1 # 删除边起点所在的斜线编号 best = INF for u, v, w in all_edges_by_level[level]: if (u, v, u + dr, v + dc) == (x1, y1, x2, y2): continue best = min(best, w) print(dist[n][n] - dead_w + best)

要注意all_edges_by_level要在读边权时同步建好，key 是斜线编号，value 是该斜线出发的所有向右/向下边的权值。查询时直接在对应编号的列表里扫一遍，每次枚举该层的所有边是 O(n)，总复杂度 O(n²+q)。如果再把每层边权排序，查询时二分或取次小值，能进一步省到接近 O(q log n)，但初中组范围内 O(n²+q) 已经足够稳。

3.3 stone 的贪心合并：平均值比较和两个方向的单调栈

石子这题是四道里最难啃的。先限制在 l=r 的场景：给定一个起点，每次向左右相邻位置合并，问最小体力。这里最反直觉的结论是：当前合并区间旁的最小值一定会立刻被合并，不需要犹豫。

稍微推导一下：设已经合并出一个连续区间，区间总和为 S。它的左右两侧各有一些未合并的点，其中最小值若紧贴区间，那它一定是下一步的最优选择。但如果最小值不紧贴，而是隔了几个点，那么那几个点会先被依次并进来，直到最小点变成紧贴状态，然后马上被合并。把“最小值隔开的那一串点”看成一个聚合块，它一定紧跟在整个合并区间后面被处理。

比较两个聚合块谁先被合并，要比的是它们内部 ai 的平均值：平均值小的块先并入合并区间更优。这样整个问题就可以用两个单调栈来维护——起点左边从内往外扫，起点右边从外往内扫，栈内聚合块的平均值从栈顶到栈底递增。每次合并时，比较左栈顶和右栈顶的平均值，选小的那个取出来并入当前区间。

# stone.py：固定起点的左右单调栈维护（完整代价用前缀和辅助计算） def push_block(stack, block): # block 是聚合块，用 (sum, cnt) 表示；平均值比较统一转成乘法 while stack and stack[-1][0] * block[1] > block[0] * stack[-1][1]: top = stack.pop() # 栈顶平均值比新块大，需要先合并 block = (block[0] + top[0], block[1] + top[1]) # 实际体力累加还需根据题目代价公式补上，核心是先处理逆序 stack.append(block) # 每次选左右栈顶平均值较小的那个，合并进当前区间 while left_stack and right_stack: if left_stack[-1][0] * right_stack[-1][1] < right_stack[-1][0] * left_stack[-1][1]: merge(left_stack.pop()) else: merge(right_stack.pop())

这段代码最值得抄的是平均值比较的方式：绝不用a/b > c/d，而是写成a * d > c * b，全程整数运算，既避免浮点误差又避免除零。block用二元组表示，第一维是聚合块内所有 ai 的和，第二维是点的个数。合并时如果栈顶平均值大于新块平均值，说明先合并栈顶更优，于是把它们揉成一个更大的聚合块，重新参与比较。

3.4 随机数据让栈变小：O(n log n) 的预处理边界

单点场景能做到 O(n) 扫出两个栈，但 q 次询问如果每个点都重新建栈，总复杂度会回到 O(nq)。题解里的关键观察是数据随机时，单调栈的期望高度只有 O(log n)。也就是说，每个位置左右两侧的栈不用全部保存，只需保存比较小的那一部分，查询时把两侧残留的栈顶拿出来比大小即可。预处理所有位置的总时空开销是 O(n log n)，查询再叠加一次栈顶比较，整体可行。

如果出题人不讲武德，把数据改成完全有序，栈高度就会退化成 O(n)。这时可以额外维护可持久化栈或分块结构，但那就超出初中组考察范围了，竞赛题解里也不是重点。做题时我一般会先按随机数据假设写一版，再故意构造单调递增/递减数据自测，如果栈真的爆了，再回头想能不能用“只存前 k 层”之类的近似方案压一压。

4. 避坑排查手记：四道题最容易翻车的五个细节

4.1 浮点数平均分当排序键导致名次颠倒

现象：本地用小数据测 score 全对，一上大数据名次和标准答案差一位。仔细比对数才发现，有两名选手的总分明明相同，但浮点平均分计算时因为舍入误差出现了微小差异，排序结果被翻转。

原因：total / (m - 2)得到的浮点数不是精确值，尤其当 total 在 int 边界附近时，末位误差会被排序比较放大。本来应该并列的选手被强行排出先后。

解决：排序阶段一律用去极值后的整数总分做键，等排序完毕、确定名次后，只在输出平均分的时刻做一次除法。如果题目要求输出平均分，也优先用格式化字符串保留足够位，不要用浮点相等去判断并列。

4.2 count 双指针右端点没有随 i 重置

现象：写出来的 O(n²) 双指针在小 n 时答案正确，换到 n=1000 以上答案突然偏大，而且错误量不是固定的。

原因：把 k 指针定义在了外层 i 循环之前，导致上一组 i 处理完的右端点延续到下一组 i。新的 i 对应更小的 a[i]，合法右端点应当回缩，但 k 停在原来靠右的位置，把一批本不合格的长木棍也算进 ans。

解决：每个 i 循环开头将 k 重置为 i+1。如果担心反复重置增加常数，可以放心，内层 while 依然只向右移动，每个 i 循环内是均摊 O(n)，整体仍为 O(n²)。我在写这类双指针时会在重置语句旁边加注释“这一行不能省”。

4.3 walk 删除边不在最短路上时误判需要重算

现象：q 次查询全部超时，但单独跑 DP 又很快。

原因：实现时先跑了一遍全局最短路，然后对每个查询判断“删除边在不在最短路上”，判断逻辑写反了。删除边明明不在最短路集合里，代码却进入替代边枚举逻辑，甚至直接重跑全局 DP，把 O(n²+q) 活生生做成了 O(qn²)。

解决：先建立shortest_set哈希集合，查询时第一件事就是集合查找。不在集合里的边直接输出原最短路长度，continue 掉。这个分支必须放在最前面，而且要用边而不是点做 key，否则两条边共享同一个端点会导致误判。

4.4 用小数比较平均值导致石子题稳定出错

现象：stone 代码逻辑和题解一致，但输出总是差一点点，且错的全是横跨多个聚合块的合并。

原因：在比较左栈顶和右栈顶谁的平均值更小时，用了float(a) / b < float(c) / d。分子分母一大，浮点数精度就不够，尤其两个平均值非常接近时，比较结果随机翻转，贪心顺序被打乱。

解决：把a/b < c/d改成a*d < c*b，或用(a, b)的分式结构存进自定义类，实现__lt__时交叉相乘。这个改法在 count 的三角形判断里同样适用，凡是涉及“谁先谁后”的比较，一律整数化。

4.5 忽略 int64 导致隐藏溢出

现象：count 题目的答案在大 n 时变成负数，score 题目的 total 明明不大，但最后排名错误。

原因：C++ 的int是 32 位，count 最坏答案接近 1.6×10^14，早超上限；score 的 sum(a) 也可能随 m 增大到 10^9 以上，与 min、max 计算时出现未定义行为。Python 虽然没有溢出，但 C++ 提交版本会直接 WA。

解决：开始写代码之前就把 n、m、q 的上限写在注释第一行，推测答案量级。任何涉及累加、乘法、组合数的变量直接开long long，不要在出错后再回头排查类型。我现在的习惯是默认所有中间变量都用 64 位，只在确认不可能超过 int 时才退回去。

5. 进阶验证：写一个对拍脚本确认四种算法都站得住

题解读完了，代码也写完了，最怕的是“思路对但实现细节错”。尤其双指针、单调栈这类结构，边界错一个符号就是全盘皆输。我常用的验证手段是对拍：写一个纯暴力的参考实现，再和优化实现随机生成小数据对比，跑几千组，直到所有结果一致。

以 count 为例，暴力版本就是三层循环枚举所有三元组，O(n³)，但 n 不超过 10 时跑得飞快；优化版本是前面写的双指针。对拍脚本随机生成 3 到 10 根木棍，长度在 1 到 100 之间：

# 对拍示例：count 题的 O(n³) 暴力版 与 O(n²) 双指针版 import random def brute(a): ans = 0 for i in range(len(a)): for j in range(i + 1, len(a)): for k in range(j + 1, len(a)): if a[i] + a[j] > a[k] and a[i] + a[k] > a[j] and a[j] + a[k] > a[i]: ans += 1 return ans def fast(a): a = sorted(a) ans = 0 for i in range(len(a) - 2): k = i + 1 for j in range(i + 1, len(a) - 1): while k + 1 < len(a) and a[k + 1] < a[i] + a[j]: k += 1 if k > j: ans += k - j return ans for _ in range(2000): a = [random.randint(1, 50) for _ in range(random.randint(3, 9))] if brute(a) != fast(a): print("mismatch", a, brute(a), fast(a)) break else: print("all ok")

随机数据能覆盖大多数普通路径，但覆盖不了恶意构造的边界。所以除了随机对拍，我还会手动构造几组特殊数据：全部相同值、严格递增、严格递减、只有两根能组成三角形、所有木棍都满足 a[i]+a[j]==a[k]。这些数据分别用来验证等号处理、双指针重置、三角形条件是否真的只用一条就能成立。stone 和 walk 也一样，做法是先写一个直接模拟的暴力版，再把优化版的输出和暴力版比对，哪怕只跑 n=5 的小格子也足够揪出八成以上的逻辑错误。

我从那次 count 题忘记重置 k 之后，每一道算法题都强制自己先写对拍再提交，浪费的时间远比想象中少。希望这个习惯也能帮到你。

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