简介“科大国创杯”2023年安徽省青少年信息学科普日活动ACSP-J组赛题解析PDF面向初中生编程竞赛选手与信息学教练内容聚焦算法设计与问题求解能力训练。资源为单个PDF文档压缩包大小约106KB全文共4页系统拆解评分、数数、行走、石子四道赛题覆盖模拟、排序、双指针、最短路径、贪心与区间合并等核心算法。每题均给出思路分析与时间复杂度评估如评分题采用去极值后求平均的O(nmn log n)做法数数题利用排序与双指针在O(n^2)内完成合法三角形计数行走题针对动态删边场景给出O(n^2q)的最短路维护方案。已有1313人学习下载适合备赛冲刺、算法专题复习或作为校内集训讲义使用对理解竞赛常见模型与优化技巧有直接参考价值。1. 竞赛算法题不是玄学从 ACSP-J 的四个题解里挖可复现套路入门级竞赛算法题往往比很多人想象的更朴素它考的不是冷门数据结构而是把常见模型用得准不准。这套省级青少年信息学科普活动 ACSP-J 组的题解恰好涵盖模拟、排序、双指针、最短路、贪心加栈五个基础模型而且每个模型都有一处容易让人卡住的细节。评分题考的是“只算总分不存数组”的边界意识数数题考的是双指针为什么能压到 O(n²)行走题考的是删边之后为什么不用重跑最短路石子题则是最难啃的贪心合并。下面逐题拆开每一步都能照着复现也会把翻车点标出来。2. 评分题模拟题的边界往往藏在约束里2.1 为什么“只算总分不存数组”是对的第一题通常是整场比赛最不该丢分的题但恰恰是这种题最容易因为想复杂而写错。题目要求对每个选手去掉一个最高分、一个最低分再算平均分。很多第一次写的人会开一个数组存下所有评委的分数然后排序、掐头去尾再求平均。这个做法不是不能过但它有两个问题一是排序引入了 O(m log m) 的额外开销二是在思路上绕远了。这题的关键约束是评委个数一样也就是说每个选手的分数数量相同。既然去掉的永远是最大和最小那中间那些分数到底长什么样根本不重要你只需要维护三个量总分、最大值、最小值。这就是模拟题的核心思维先想清楚“输出到底依赖哪些信息”再决定要维护什么状态而不是把题面给的数据原样存下来。顺着这个思路每个选手只需要在线读入 m 个分数一边累加一边更新最大最小。读完之后总分减去最大值和最小值再除以 m − 2 就是平均分。整个过程不需要数组不需要排序连等于最大值的多个分数都不需要特殊处理减掉一个最大值和一个最小值即可。2.2 评分代码与逐行拆解#include bits/stdc.h using namespace std; int main() { int n, m; scanf(%d%d, n, m); for (int i 1; i n; i) { long long sum 0; int x; scanf(%d, x); int mx x, mn x; // 用第一个分数初始化最大最小 sum x; for (int j 2; j m; j) { scanf(%d, x); sum x; if (x mx) mx x; if (x mn) mn x; } double avg (double)(sum - mx - mn) / (m - 2); printf(%.2f\n, avg); } return 0; }这里有个细节值得单独说最大值和最小值不是初始化成 0 和 100而是用第一个读入的分数初始化。如果题目给的分数是负数或者分数上限不是 1000 和 100 的初始化就会直接让答案错掉。用第一个分数初始化是最稳的写法可以覆盖任何分数范围。avg 的计算也刻意先做整数减法再转 double避免浮点误差在累加阶段被放大。时间复杂度和题解里说的一致每个选手 O(m)再加上输入输出整体就是 O(nm)比排序做法还少一个 log。2.3 模拟题最容易翻车的三个边界现象一m 等于 2 或更小时程序直接崩溃或者输出 NaN。原因很简单m − 2 是除数m 2 时除数为零m 1 时会减掉两个不存在的分数。解决方法是读完 n 和 m 之后先判断如果 m 2按题目要求的兜底规则处理一般直接输出总分除以 m。现象二某个选手只有一次得分或者所有分数相同去最大最小后剩余个数为零。比如 m 1 时算平均分在数学上没有意义。这类边界在样例里通常不会出现但构造数据时专门卡你。解决方法是明确题目对 m 的下界有没有保证没有的话就要特判。现象三总分用 int 存n 和 m 稍大就溢出。这个属于见得多但每次都有人犯的错。每个分数虽然不大但 m 个分数累加后可能超过 int 范围保险起见直接用 long long。模拟题的边界就藏在约束里把约束先读透再动手能省掉后面一大半调试时间。3. 数数题排序加双指针把三角形判定压到 O(n²)3.1 先排序再枚举双指针的右端点为什么单调第二题问的是从一堆木棍里选三根组成三角形。三边能否成三角形的朴素判断是任意两边之和大于第三边但直接这样判断会产生大量重复枚举。常规做法是先把长度排序得到 a1 ≤ a2 ≤ … ≤ an这样只要满足较短两根之和大于最长那根三边关系自动成立。具体枚举方式是固定两根较短的木棍 i 和 j其中 i j然后找所有满足 k j 且 a[k] a[i] a[j] 的位置 k。这里 k 的取值是一个区间左端点是 j 1右端点需要满足 a[k] 严格小于两边之和。如果对每个 j 都重新二分找右端点复杂度是 O(n² log n)能过但不够优雅。真正让复杂度降到 O(n²) 的是双指针的单调性固定 i 时随着 j 增大a[i] a[j] 也在增大所以合法 k 的右端点只会向右移动不会回退。于是可以维护一个指针 k在 j 增大的过程中不断把 k 往右推。这个“指针只能前进不能后退”的性质正是双指针能取代二分的前提。3.2 完整代码与 k 的移动逻辑#include bits/stdc.h using namespace std; const int N 5005; int a[N]; int main() { int n; scanf(%d, n); for (int i 1; i n; i) { scanf(%d, a[i]); } sort(a 1, a n 1); long long ans 0; for (int i 1; i n; i) { int k i; // k 指向合法区间的右端点 for (int j i 1; j n; j) { if (k j) k j; // 右端点至少要从 j 之后开始 while (k 1 n a[k 1] a[i] a[j]) { k; // 只要下一个还满足就继续推 } if (k j) { ans k - j; // j1 到 k 全部是合法的最长边 } } } printf(%lld\n, ans); return 0; }代码里 k 的作用是当前合法区间的右边界。内层 j 每右移一次a[i] a[j] 变大原有的 k 仍然合法所以不用重置只在现有基础上继续向右扩展。ans 累加的是 k − j因为 j 1 到 k 这些位置都可以作为最长边数量正好是 k − j。整体复杂度 O(n²)排序部分 O(n log n)在 n 到几千的范围内跑起来很快。3.3 三角形判定的两个隐蔽坑现象一把a[k 1] a[i] a[j]写成了a[k 1] a[i] a[j]样例可能不变但构造一个等腰退化三角形就会多算。原因是三角形要求严格不等式两边之和等于第三边时三根木棍拼不成三角形。解决方法是严格使用这个细节在题解里写得明确但自己实现时特别容易顺手写成。现象二ans 用了 int数据一大就溢出。原因很简单O(n²) 枚举下答案的规模是 n² 级别的n 5000 时可能接近千万n 更大时 int 就不够了。解决方法是累加变量统一用 long long包括排序后的数组值如果很大比较时也可能需要 long long 参与运算。现象三k 的初始化位置不对导致漏解。有人会在每个 j 循环里把 k 重置成 j 1这样虽然正确但每次都重新扫描复杂度退化回 O(n³)。这题的双指针优化前提就是 k 不重置让它在 j 循环中持续前进。4. 行走题删边最短路别重跑按斜线层找替代边4.1 网格最短路的层结构第三题是个图论问题但考法很特别。网格图中从 (1,1) 走到 (n,n)每一步只能向下或向右问每次删除一条边之后的最短路。最容易想到的做法是每次询问都重新跑一遍最短路但这样复杂度是 O(q × n²)询问一多就超时。先看路径的固定结构。把网格中的点按 x y 的值分组所有满足 x y c 的点在同一条斜线上。从 (1,1) 出发每走一步 x y 恰好增加 1所以任意一条路径都是按斜线层逐层推进的先经过 x y 2 这一层再到 x y 3一直到 x y 2n。每一条边连接的其实是相邻两层斜线之间的点。这个观察的价值在于删掉一条边之后受影响的只是它所在的那一层“层间通道”。如果这一层还有其他边可以连接同样的两层那么路径完全可以绕过去而且绕行后步数仍然是 2n − 2。换句话说网格里所有合法路径的长度天然相同最短路的长度就是 2n − 2关键在于删除某条边之后是否还存在一条完整的路径。4.2 删边后的三种情况与答案判定判断删边的影响要先求出一条初始最短路。这里可以用动态规划从 (1,1) 和 (n,n) 两个方向分别预处理距离得到每个点到起点的最短距离 d1 和到终点的最短距离 d2。一条边 (u,v) 在最短路上当且仅当 d1[u] 1 d2[v] 等于原始最短路长度。删边情况判定方法输出边不在任何最短路上d1[u] 1 d2[v] 原长度直接输出原最短路长度在最短路但所在层有其他边该层边数大于 1路径仍然连通输出原长度所在层只剩这一条边该层边数等于 1无替代边需要重新求最短路或输出不可达第三种情况很重要但也最容易被忽略。因为路径必须经过每一层斜线间隙如果某一层的所有边都被删光那从起点到终点就不可能连通。实际处理时可以对每一层统计边数回答询问时只需要看删掉的边所在层的剩余边数是否大于零。4.3 实现要点与替代边的预处理// 假设已经用 BFS/DP 求出 d1 和 d2 // edgeLayer 记录每条边所在的斜线层 // layerCnt[t] 表示第 t 层总边数 int D d1[n][n]; // 原始最短路长度 bool onShortestPath(int u, int v) { return d1[u] 1 d2[v] D; } int query(int u, int v) { if (!onShortestPath(u, v)) { return D; // 删的边不影响最短路 } int t edgeLayer[u][v]; if (layerCnt[t] 1) { return D; // 同层还有替代边 } // 同层只剩这一条边需要重新计算最短路或判定不可达 return rebuildShortestPath(); }这里最关键的一点是判断删边是否在最短路上的公式里必须保证 u 到 v 的方向是从靠近起点一侧指向靠近终点一侧。网格中每条边天然满足 x y 增加的方向所以方向判断不会错但如果你把边的两个端点写反了d1[u] 1 d2[v] 就恒不等于 D所有边都会被判成“不在最短路上”。预处理每层边数可以用一个二维数组或者哈希表存层号到边数的映射遍历所有边累加即可。整体复杂度 O(n² q)这里的 n² 是预处理网格边数的开销每次询问 O(1) 回答这才是这题真正考察的点。5. 石子题贪心合并的栈结构是全场最难的 O(n log n)5.1 固定区间时“先合并谁”的贪心推导最后这题是整套题里最有嚼头的一道。它问的是在一个区间内从某个点开始不断向左或向右合并石子每次合并的花费和当前区间规模相关求最小总花费。题解里先说清楚 l r 的简化情形也就是固定初始点然后逐渐把两边还没有合并的石子并入当前区间。贪心的直观想法是如果当前还没合并的石子里最小值正好在当前区间的左边或者右边那一定先合并它。但如果最小值隔着一些点情况就复杂了。比如最小值在左边但中间隔了几个点那这几个点一定会在最小值之前被合并因为合并的方向是逐格推进的。这给了题解一个关键结论最小值和它右侧的一串点可以打包看成一个块因为它们在合并顺序上必然紧挨着。合并两个块的时候需要比较谁先并入当前区间更划算。设块 X 有 x 个点、点权和为 sumX块 Y 有 y 个点、点权和为 sumY当前区间点权和为 S。先并入 X 再并入 Y 的花费是 x·S y·(S sumX) 加上两个块的内部贡献先并入 Y 再并入 X 的花费是 y·S x·(S sumY)。两者做差化简后得到 x·y 乘以 avgX 减去 avgY 的差。也就是说平均值更小的块先合并总花费一定更小。这个用交换法推出来的结论是整个贪心策略的地基。5.2 平均值比较与栈的维护规则有了“平均值小的先合并”这个结论剩下的问题就是如何高效维护待合并块的顺序。对初始点左边的点从左往右扫描用栈来维护已经打包好的块。每加入一个新块就把它放在栈顶然后比较栈顶和栈顶下一个的平均值。如果栈顶平均值大于下一个说明较靠内侧的块更“重”应该先和靠外侧的块合并于是把两个块合成一个新块继续和更下面一个比较直到栈顶平均值不再大于下一个为止。初始点右边的点从右往左做同样的操作。这样处理完之后两边各得到一个栈而且这两个栈从栈顶到栈底平均值递增栈顶是平均值最小的块。每次合并时只需要比较左右两个栈顶的平均值取较小的那个先合并。这个选择可以反复进行每次合并都会更新对应栈顶的 sum 和 cnt再和新的下一个继续比较。整个过程的花费可以顺便累加进答案。struct Block { long long sum; int cnt; }; // 比较两个块的平均值不用浮点用交叉相乘 bool avgLess(const Block a, const Block b) { return a.sum * b.cnt b.sum * a.cnt; } Block mergeBlock(const Block a, const Block b) { return Block{a.sum b.sum, a.cnt b.cnt}; }这段代码刻意没有写完整的主流程因为核心逻辑就是栈顶的反复比较和合并。avgLess 里的交叉相乘很关键直接拿 double 比较平均值在大数情况下精度会悄悄吃掉正确性这是这类贪心题最容易踩的坑。如果某个块的平均值更小就让它先并入区间合并后的 block 作为新的栈顶继续参与后续比较。5.3 实现层面的三个防炸细节现象一平均值比较用浮点答案在边界数据上差一个数。原因是大整数相除后小数位丢失两个本来不同的平均值可能在 double 下变成相等。解决方法是始终用a.sum * b.cnt和b.sum * a.cnt做整数比较全程不碰浮点。现象二栈合并的方向写反左边扫描出来的栈顺序不对。原因是“从左往右扫”和“栈顶是最靠近初始点”这两件事容易混淆。解决方法是先手推一个长度为 5 的小例子把入栈和合并的每一步画出来确认栈顶确实代表“下一个要并入区间的候选块”再写代码。现象三数据不随机时栈会退化。题解里特别提到随机数据下栈的大小是 O(log n)所以才能做到 O(n log n) 的时空复杂度。但你要知道这个复杂度结论是有前提的如果题目数据是构造出来专门卡栈的栈会膨胀到 O(n)记录所有位置的左右栈就不再可行。实际考场里遇到这种情况先把暴力版本写出来对拍确认贪心方向没错再考虑是否要扩展维护额外的信息。6. 避坑实战三个高频翻车点与一套对拍验证脚本6.1 三分钟搭起一个对拍循环竞赛题写完之后最怕的不是思路错而是思路对但实现里藏了一个细微的边界错误。对拍是解决这个问题最直接的手段它的原理很简单写一个暴力程序和一个数据生成器不断生成小数据用暴力程序的结果作为标准答案和你的正解程序输出做对比。#!/bin/bash for i in $(seq 1 10000); do ./gen data.in ./brute data.in ans.out ./solve data.in res.out if ! diff -q ans.out res.out /dev/null; then echo WA on test $i break fi done echo all tests passedgen 是数据生成器brute 是暴力程序solve 是待验证的正解。这个脚本会循环一万次每次生成新数据比较两个程序的输出。第一次跑通之后你就有了一个能自动找反例的工具之后每改一次正解代码重新跑一遍对拍脚本能在几十秒内暴露大部分实现错误。6.2 数据生成器怎么设计反例数据生成器是对拍的关键它的质量直接决定你能找出什么样的 bug。最常见的错误是生成器只出均匀随机的小数据这样能抓到普通错误但抓不到边界问题。我一般会在生成器里混合多种数据n 1 或 n 2 的最小规模、所有值相同、所有值递减、最大值和最小值混在一起、以及完全随机的数据。对石子这类贪心题还要专门构造那些会让栈连续合并的序列比如前半段递增后半段递减专门刺激栈的合并逻辑。6.3 三次对拍翻车留下的教训第一次是调试信息混进标准输出。为了看中间变量我在正解里写了不少 printf结果 diff 永远报错当时还以为是思路错了查了半天才发现是调试输出污染了结果。从那以后我把所有调试信息都写到 stderr标准输出只留最终答案。第二次是数据生成器忘了覆盖极端边界。对拍跑了两万组全过一提交就 WA。原因是生成器的 n 最小只随机到 3而题目允许 n 1边界路径完全没测到。从那以后我在生成器里显式加入最小规模和最大规模的测试点再配合随机数据一起跑。第三次是改了代码忘了重新编译对拍脚本跑的是旧的二进制文件。这个问题尤其隐蔽因为程序可能照样输出正确结果也可能因为旧代码有 bug 而反复报错白白浪费大量时间。从那以后我每次写完一道题不管自我感觉多稳都会先花十分钟把对拍脚本搭起来再提交编译、生成、对比三步强制走一遍省下来的调试时间远超那十分钟。希望帮到你。本文还有配套的精品资源点击获取