简介这份资源是“科大国创杯”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²)第二题是经典的“三根木棍能拼成三角形”计数。暴力枚举 ijk 再判断 a[i]a[j]a[k]复杂度 O(n³)n 稍微大一点就超时。正确做法是先排序固定较短的两根 i、j那么最长的 k 必须满足 kj 且 a[k] a[i]a[j]。因为数组有序合法的 k 是一段连续区间左端点固定为 j1右端点随着 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必须强制拉到 j1。另外计数时是k - j - 1因为合法区间是 [j1, k-1]。面试时如果被问“为什么双指针不会漏”答“排序后不等式具有单调性右端点随 j 增大只右移”即可。2.3 行走walk删边最短路先找一条最短路再按斜线替换第三题是网格图上的删边最短路。题意是每次删一条边问从 (1,1) 到 (n,n) 只向下或向右走的最短路。关键观察如果删的边不在某条最短路上答案不变如果删的边在最短路上由于网格图每条路径长度固定为 2n-2删掉一条边后只需要找一条“替代边”绕过去。把网格按 xy 分层每条边连接相邻两层删掉某条边后枚举同一层之间的其他边替换即可。# 核心思路示意先求一条最短路记录路径上的边 # 对路径上的每条边枚举同层替代边取最小增量 # 时间复杂度 O(n^2 q)这段伪代码的重点不是逐行实现而是理解“分层替换”的建模网格图里所有从 (1,1) 到 (n,n) 的路径都经过每一层恰好一次所以删边的影响局限在相邻两层之间。面试官常追问“为什么复杂度是 O(n²q)”答“预处理每条路径边被删后的替代代价是 O(n²)每次询问 O(1) 查表”。易错点是忘记判断删边是否在最短路上导致对不在路径上的边也去重算白白超时。2.4 石子stone贪心合并与单调栈O(n log n) 的思维题压轴题“石子”是整套卷子里最考思维的一道。先看 lr 的简化版给定一个起点每次把相邻两堆合并花费是两堆石子数之和求最小总花费。贪心结论是如果当前未合并区间的最小值在已合并区间的左边或右边一定先合并它如果最小值不在旁边就把它和它右边的点“打包”成一个整体因为它们在最优方案里一定紧接着一起合并。打包后的整体可以按“内部平均值”比较先后平均值小的先合并更优。于是对起点左边从左往右扫、维护一个单调栈栈顶平均值大于下一项就合并右边从右往左同理。每次询问取左右栈顶平均值较小的那个合并。# 单调栈维护“打包块”每块记录 (石子总和, 块内点数) # 合并条件栈顶块的平均值 栈中下一块的平均值 # 询问时双指针从左右栈顶取平均更小者合并这类题面试官最想听的是“你为什么敢打包”因为最小值旁边的点被合并后下一步必然轮到最小值所以它们可以视为一个整体且整体内部的合并顺序不影响外部比较。易错点在于只比较单点石子数而忽略“块内点数”对花费的放大效应——合并一个含 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 从 i2 开始内层 j 增大时没有检查k j导致 k 落在 j 左边k - j - 1变成负数。为什么错右端点指针的单调性只在“合法区间右端”上成立j 追上 k 时必须强制把 k 拉到 j1。怎么答对内层循环开头加一句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. 答题节奏与押题思路从签到到压轴的时间分配表真正上了考场四道题的节奏比单独会做更重要。我的习惯是开考先花三分钟通读全卷确认“评分”是纯模拟、“数数”是排序双指针、“行走”是图论建模、“石子”是贪心栈然后按下面的时间表推进阶段题目建议用时目标检查动作第一轮评分10 分钟拿满手算一组含重复极值的样例第一轮数数25 分钟拿满小数据对拍暴力 O(n³)第二轮行走35 分钟拿大部分验证删边在/不在最短路两种情况第三轮石子40 分钟拿随机分先写 lr 的 O(n) 版本再扩展收尾全部10 分钟防低级错检查输出格式、边界、数组越界这张表的核心逻辑是“先保底再冲高”评分和数数必须一次写对行走拿到“删边不在最短路”的送分部分石子先写简化版拿部分分。押题方向上这类普及组卷子每年必考“排序双指针”和“网格图最短路”而“贪心单调栈”是拉开档次的区分题。复习时不要只背代码要练“看到删边最短路先想分层替换”“看到合并花费先想平均值比较”这两个条件反射。从那以后我每次带人刷这套题都强制先手写一遍评分的极值维护和数数的双指针边界再上机跑对拍——血泪经验是签到题翻车比压轴题不会更伤士气。希望帮到你。本文还有配套的精品资源点击获取