企业官网建设流程全解析

简介：“科大国创杯”2023年安徽省青少年信息学科普日活动ACSP-J组赛题解析PDF，面向初中生编程竞赛选手与信息学教练，内容聚焦算法设计与问题求解能力训练。资源为单个PDF文档，压缩包大小约106KB，全文共4页，系统拆解评分、数数、行走、石子四道赛题，覆盖模拟、排序、双指针、最短路径、贪心与区间合并等核心算法。每题均给出思路分析与时间复杂度评估，如评分题采用去极值后求平均的O(nm+n log n)做法，数数题利用排序与双指针在O(n^2)内完成合法三角形计数，行走题针对动态删边场景给出O(n^2+q)的最短路维护方案。已有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，而是用第一个读入的分数初始化。如果题目给的分数是负数，或者分数上限不是 100，0 和 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; // j+1 到 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] 等于原始最短路长度。

第三种情况很重要但也最容易被忽略。因为路径必须经过每一层斜线间隙，如果某一层的所有边都被删光，那从起点到终点就不可能连通。实际处理时，可以对每一层统计边数，回答询问时只需要看删掉的边所在层的剩余边数是否大于零。

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 passed"

gen 是数据生成器，brute 是暴力程序，solve 是待验证的正解。这个脚本会循环一万次，每次生成新数据，比较两个程序的输出。第一次跑通之后，你就有了一个能自动找反例的工具，之后每改一次正解代码，重新跑一遍对拍脚本，能在几十秒内暴露大部分实现错误。

6.2 数据生成器怎么设计反例

数据生成器是对拍的关键，它的质量直接决定你能找出什么样的 bug。最常见的错误是生成器只出均匀随机的小数据，这样能抓到普通错误，但抓不到边界问题。我一般会在生成器里混合多种数据：n = 1 或 n = 2 的最小规模、所有值相同、所有值递减、最大值和最小值混在一起、以及完全随机的数据。对石子这类贪心题，还要专门构造那些会让栈连续合并的序列，比如前半段递增后半段递减，专门刺激栈的合并逻辑。

6.3 三次对拍翻车留下的教训

第一次是调试信息混进标准输出。为了看中间变量，我在正解里写了不少 printf，结果 diff 永远报错，当时还以为是思路错了，查了半天才发现是调试输出污染了结果。从那以后我把所有调试信息都写到 stderr，标准输出只留最终答案。

第二次是数据生成器忘了覆盖极端边界。对拍跑了两万组全过，一提交就 WA。原因是生成器的 n 最小只随机到 3，而题目允许 n = 1，边界路径完全没测到。从那以后我在生成器里显式加入最小规模和最大规模的测试点，再配合随机数据一起跑。

第三次是改了代码忘了重新编译，对拍脚本跑的是旧的二进制文件。这个问题尤其隐蔽，因为程序可能照样输出正确结果，也可能因为旧代码有 bug 而反复报错，白白浪费大量时间。从那以后我每次写完一道题，不管自我感觉多稳，都会先花十分钟把对拍脚本搭起来再提交，编译、生成、对比三步强制走一遍，省下来的调试时间远超那十分钟。希望帮到你。

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