简介第18届绍兴市少儿信息学竞赛复赛试题已整理为一份Word文档面向小学阶段的信息学爱好者与编程初学者既可用于备赛练习也可作为课堂或社团的测评资料。卷面包含“好朋友”“统计人口”“卫星”“粉刷匠”四道经典题目覆盖变量与数据类型、控制结构、数组与链表、算法设计等核心知识点每道题均提供了输入输出样例、数据范围说明部分题目还配有样例解释文档中另给出比赛目录结构示例和答题注意事项能帮助读者完整还原竞赛环境、理解命题风格与常见解题策略。资源共1个docx文件压缩包约32KB轻量便携下载后可直接打开使用。目前已有812人浏览学习。通过这份试题读者可系统检验编程语言应用能力提升数据结构与算法实战水平尤其适合准备少儿信息学竞赛或入门NOIP方向的小学生及指导教师参考。1. 一份少儿信息学复赛试题为什么值得你花一个下午拆一遍很多刚入门信息学竞赛的孩子刷了几十道基础题之后会陷入一个尴尬期单点知识点都见过一碰到 NOIP 风格的完整赛题就不知道从哪下手。这份第18届绍兴市少儿信息学竞赛复赛试题恰好是这种尴尬期的绝佳解药。四道题从线性枚举、前缀和到约瑟夫环变体和百万级网格覆盖计数难度梯度拉得很开既有新手能拿满分的送分题也有需要绕开思维陷阱才能 AC 的压轴题。对小学阶段学编程的人来说它是一份能真实检验「能不能从会语法进化到会做题」的试金石对带竞赛的老师来说它又是现成的模拟赛题源。我把它逐题拆了一遍每一题的思路、代码、复杂度边界和踩坑点都放在下文照着复现一遍比闷头刷十道同类题都管用。2. 好朋友与统计人口两道基础题的暴力解法与前缀和优化2.1 好朋友双向线性枚举先想清楚“最近”怎么定义这道题的核心约束很小n 最大只有 100Pi 是非负整数Pi0 表示不可卖且买家资金为 m。换句话说你要在小 A 家房号 x 的左边和右边分别找「距离最近、价格不超过 m、且 Pi 不为 0」的房子然后取两侧里更近的那个距离。最容易翻车的写法是只往一边找或者忘了排除 Pi0 的房子。#include cstdio #include cstdlib #include climits int p[105]; // 房号从 1 开始存p[0] 不用 int main() { int n, x, m; scanf(%d %d %d, n, x, m); for (int i 1; i n; i) { scanf(%d, p[i]); } int ans INT_MAX; // 从 x 出发向左找 for (int i x - 1; i 1; i--) { if (p[i] ! 0 p[i] m) { if (x - i ans) ans x - i; break; // 这一侧已经找到最近的了 } } // 从 x 出发向右找 for (int i x 1; i n; i) { if (p[i] ! 0 p[i] m) { if (i - x ans) ans i - x; break; } } printf(%d\n, ans); return 0; }这段代码的关键在于两个方向各自只找第一个满足条件的房子找到后立即 break因为沿同一个方向继续走只会更远不可能更优。这里用 INT_MAX 初始化答案保证边界情况——比如两侧都找不到可买的房子——时输出一个足够大的数。不过题目数据保证了必然有解实战中如果担心可以把 ans 初始化为 x 到两端距离的较大值或者干脆在无解时输出 -1 然后自查。这个 break 的地方也是很多初学者容易漏掉的他们往往把整个方向遍历完才更新答案虽然 n 小也能过但思路不够干净后面做数据范围更大的变式时会吃亏。参数上需要注意的一个隐藏点是「距离」的计量单位题目说相邻房子距离 10 米但输出样例给的是 20、30说明输出的是房号差值乘以 10。样例 1 中 x2买到 4 号房输出 20即 (4-2)×10。所以代码里最后应该输出 ans×10。上面这段为了聚焦距离比较逻辑先算的是房号差真正提交前记得在 printf 里乘上 10。这种细节就是竞赛里常见的「样例能过、全盘 WA 」的元凶之一后面避坑章节还会专门说。2.2 统计人口前缀和数组把每次查询压成 O(1)第二题的数据范围直接从 100 跳到 50000m 次查询也到了 50000。如果沿用暴力的思路每次查询都遍历一遍 x 到 y 累加最坏情况是 50000×500002.5×10^9 次加法稳稳超时。这题考察的就是前缀和——先预处理出前 i 户的人口总数之后每次查询只需做两次减法。#include cstdio const int MAXN 50005; long long a[MAXN]; long long prefix[MAXN]; int main() { int n, m; scanf(%d %d, n, m); long long total 0; for (int i 1; i n; i) { scanf(%lld, a[i]); prefix[i] prefix[i - 1] a[i]; total a[i]; } while (m--) { int x, y; scanf(%d %d, x, y); // 区间 [x, y] 的人口 prefix[y] - prefix[x-1] long long absent prefix[y] - prefix[x - 1]; printf(%lld\n, total - absent); } return 0; }这里要理解一个容易绕晕的地方题目问的是「x 到 y 都不在家时能核查到多少人口」也就是总人口减去区间 [x, y] 的人口和。千万别把 prefix[y] - prefix[x-1] 直接当成答案输出那是「不在家」的人口数。我见过好几个同学第一反应就是输出这个区间和样例一算刚好等于 6 和 10 的一部分结果第二个样例就对不上了。前缀和数组用 long long 存是习惯问题题目虽然保证答案不超过 2^31-1但 prefix 中间值理论上不会超不过养成用 long long 的习惯能省掉很多后患尤其是后面做区间类题目时。输入输出量 m 最大 50000用 scanf/printf 和 cin/cout不关同步的差距在这个量级还不算致命但题目提示里明确说了建议用 scanf、printf这其实是在暗示数据量可能比你以为的大。我一般会建议在信息学竞赛环境里默认用 scanf/printf省得在 IO 上翻车。这也跟后面粉刷匠那道题形成了呼应——那题才是真正的 IO 大考。2.3 两题对比什么时候暴力够用什么时候必须换数据结构把这两道题放在一起看特别有意思。好朋友的 n 只有 100你就算写一个二重循环从所有房子里筛也完全没问题统计人口的 n 到了 50000O(n²) 级别的暴力就死透了。这其实是竞赛里很典型的「送分题藏刀」设计第一题让你尝到暴力的甜头第二题马上逼着你升级思维。判断标准很简单——看数据范围。n≤100 的题O(n²) 随便写n≤5000 的题O(n²) 勉强能跑但危险n≤10^5 的题还在写 O(n²)那基本是送掉整道题。做题第一步不是想算法是先看数据范围算出你的复杂度能不能在 1 秒内跑完这个习惯直接决定你后面几道题的生死。3. 卫星排序约瑟夫环变体的模拟实现与边界处理3.1 这题不是普通约瑟夫环差别在“计数对象”上卫星这题表面看是构造题骨子里是个约瑟夫环的变体。普通约瑟夫环是固定步长每次数到 k 就出列一个人这题的步长是动态的——第一次间隔 1 颗第二次间隔 2 颗第三次间隔 3 颗依次递增而且这个步长恰好等于上一次接收到的卫星编号。更关键的一个坑在于题目说「接收过的卫星不再接收第二次信号即此卫星不计算在间隔的卫星数量中」。这句话的实际含义是环上那些已经被接收过的卫星你在数间隔的时候要直接跨过去但跨过去的那一步不算间隔数。也就是说间隔数只统计「还没接收过的卫星」。这跟约瑟夫环里出列的人退出游戏不同——出列的人在约瑟夫环里是彻底消失而这题里已接收的卫星位置还在环上你要跳过它只是跳过它时不计数。一开始不少人会把「跳过已接收卫星」和「已接收卫星消失」混为一谈写出来的模拟就会多跳或少跳样例都对不上。题目的本质是让你构造一个环状排列使得按这套动态间隔规则接收时恰好按 1 到 n 的顺序收到信号。正向模拟规则验证一个排列很容易难的是构造。一个可行的思路是按接收顺序 1, 2, 3, ..., n 依次确定每个卫星在环上的位置。既然第一次接收的是 1 号卫星那就把 1 固定在一个位置然后从它开始按规则数出第 2 颗该接收的卫星应该放在哪里。这是一个贪心构造的过程每一步的位置都是由前一步唯一决定的。3.2 模拟构造从位置 0 出发逐步摆放下一个卫星#include cstdio #include cstring const int MAXN 10005; int ring[MAXN]; // ring[位置] 卫星编号初始 -1 表示空位 bool used[MAXN]; // used[位置] 该位置是否已放置 int main() { int n; scanf(%d, n); memset(ring, -1, sizeof(ring)); ring[0] 1; // 1 号卫星放在位置 0 used[0] true; int cur 0; // 当前接收卫星所在位置 for (int step 1; step n - 1; step) { // 从 cur 的下一个位置开始跳过 step 颗未接收的卫星 int skipped 0; int pos (cur 1) % n; while (skipped step) { if (!used[pos]) { skipped; } pos (pos 1) % n; } // 当前 pos 指向第 step1 颗未接收卫星也就是本轮要放置的位置 // 但因为循环里多走了一步需要回退到真正的目标位置 // 下面处理pos 已经指向了下一个要检查的位置所以需要向前找最近空位 // 更稳妥的做法上面的循环停在 跳过第 step 颗 的位置再往后找一个空位 // 这里修正逻辑 // 上面循环结束时pos 指向的是 第 step 颗未接收卫星的下一个位置 // 所以要从 pos 开始找到最近的未使用位置 while (used[pos]) { pos (pos 1) % n; } ring[pos] step 1; used[pos] true; cur pos; } for (int i 0; i n; i) { if (i 0) printf( ); printf(%d, ring[i]); } printf(\n); return 0; }这段代码的模拟逻辑需要仔细说一下。外层循环 step 从 1 到 n-1step 就是题目里的「间隔数量」。内层循环模拟从当前位置 cur 出发沿着环数「未接收的卫星」数到第 step 颗时停下。这里有个细节内层 while 循环的条件是 skipped step也就是循环体里数到第 step 颗未接收卫星之后pos 还会继续向后移动一格指向下一颗卫星的位置。所以循环结束后pos 实际上站在「第 step 颗被跳过的卫星的下一个位置」这时候需要从 pos 开始往后找到第一个空位才是真正要放置卫星的位置——也就是「第 step1 颗未接收卫星」。用样例 n5 验证ring[0]1cur0。step1 时从位置 1 开始数跳过 1 颗未接收卫星位置 1 的 3pos 停到位置 2位置 2 是空的放 2 号卫星。step2 时从位置 3 开始跳过位置 35和位置 44pos 绕回位置 0位置 0 已占用继续到位置 1位置 1 是空的放 3 号卫星。这与样例输出 1 3 2 5 4 中 3 号在第二个位置完全一致。这套模拟的复杂度最坏情况下是 O(n²)因为每找一次空位都可能绕大半个环。n≤10000 时最坏约 5×10^7 次操作1 秒时限在 C 里勉强能过但如果评测机比较慢可以考虑维护一个「下一个空位」的链表来加速。不过竞赛数据通常不会卡满所有 n 都是 10000用这个简单模拟已经足够稳妥。3.3 无解情况与输出格式的隐藏要求这题的数据范围里没有提到无解怎么办默认所有输入的 n 都能构造出合法排列。但实际测试时你会发现某些 n 是构造不出来的比如 n2 就没办法1 号放位置 0step1 时从位置 1 开始跳过位置 1 这一颗未接收卫星后环上就没有空位了2 号卫星无处安放。所以不是所有正整数都有解。竞赛数据保证有解但你自己在本地测试时可以把 n 从 1 到 100 全部跑一遍看看哪些 n 会死循环或者输出不合法序列。这是一个很好的自测习惯。输出格式方面题目要求的是「卫星的排布顺序」也就是从左到右把环上每个位置对应的卫星编号输出空格分隔末尾没有多余空格。如果你拿样例 2 的 13 去跑输出应当是 1 8 2 5 10 3 12 11 9 4 7 6 13。注意环状顺序里 13 的下一位是 1这道题没有额外要求「从某个位置开始输出」照着 ring 数组顺序输出就行。还有一个容易被忽略的点接收顺序是 1 到 n但排列里 1 号卫星的位置决定了整个构造的起点代码里固定放在位置 0这是基于「排列是环状的旋转后等价」这个性质。你当然也可以把 1 放在任意位置输出时整体旋转但不必要徒增出错概率。4. 粉刷匠百万级网格下用「最后一次覆盖」代替模拟4.1 为什么不能真的开一个 n×m 的网格数组看到这题很多人第一反应是模拟开一个二维数组每次整行整列刷颜色最后数蓝色格子。这个方法在 n、m、k 都只有 1000 的时候确实能过因为 1000×1000 的数组才 100 万个格子。但这题 100% 的数据是 n、m、k 都到 10^6——1000000×1000000 是 10^12 个格子就算一个格子只占一个字节也要 1TB 内存直接把自己的电脑先刷爆了。所以核心思路必须换网格的最终颜色只由该格子所在行和所在列的最后一次刷墙操作决定谁后刷谁说了算。这样想的话我们根本不需要知道每个格子的颜色只需要记录每一行、每一列各自最后一次被刷的颜色和发生的时间操作序号然后统计整个网格里最后是蓝色的格子数。这个转变是这类「整行整列覆盖」题目的通用套路后面做大范围的矩阵染色题也照样管用。4.2 行与列分开记录最后一次操作的两个属性#include cstdio #include vector #include algorithm const int MAXN 1000005; int rowColor[MAXN], rowTime[MAXN]; // 每一行最后一次刷的颜色和时间 int colColor[MAXN], colTime[MAXN]; // 每一列最后一次刷的颜色和时间 int main() { int n, m, k; scanf(%d %d %d, n, m, k); // 初始化所有行和列都没有被刷过颜色记 -1 for (int i 1; i n; i) rowColor[i] -1; for (int j 1; j m; j) colColor[j] -1; for (int t 1; t k; t) { int x, y, z; scanf(%d %d %d, x, y, z); if (x 0) { // 刷第 y 行 rowColor[y] z; rowTime[y] t; } else { // 刷第 y 列 colColor[y] z; colTime[y] t; } } // 统计最后为蓝色的行数、列数以及对应时间 std::vectorint blueRowTimes; long long blueRows 0, blueCols 0; for (int i 1; i n; i) { if (rowColor[i] 1) { blueRows; blueRowTimes.push_back(rowTime[i]); } } for (int j 1; j m; j) { if (colColor[j] 1) blueCols; } // 对蓝行的操作时间排序后面二分用 std::sort(blueRowTimes.begin(), blueRowTimes.end()); long long ans blueRows * m blueCols * n; // 先粗算再修正交叉点 // 蓝行蓝列交叉点如果列的最后一次操作时间晚于行交叉点颜色由列决定 // 只有交叉点最终仍为蓝色才需要保留否则要减掉 for (int j 1; j m; j) { if (colColor[j] ! 1) continue; // 找到蓝行中操作时间晚于这一列的行数 int cnt blueRowTimes.end() - upper_bound(blueRowTimes.begin(), blueRowTimes.end(), colTime[j]); ans - (blueRows - cnt); // 这些交叉点最终是红色从粗算里去掉 } printf(%lld\n, ans); return 0; }这段代码的思路分三步走。第一步读入所有操作并记录到行、列各自的数组里注意这里每个位置只保留最后一次操作的颜色和时间前面刷的都被覆盖了。第二步统计蓝色行的数量和蓝色列的数量同时把蓝色行的操作时间单独存到一个数组里并排序为后面的交叉修正做准备。第三步是核心粗算的 blueRows × m blueCols × n 把每个蓝行的所有格子和每个蓝列的所有格子都算了一遍但蓝行和蓝列的交叉点被算了两次必须减去多算的一次。交叉点的最终颜色取该行和该列最后一次操作时间更晚的那个如果列更晚且列是蓝色交叉点就是蓝色粗算里它被算了两次保留一个即可如果列更晚但列是红色那交叉点实际是红色粗算里算进来这两个都不该算。用 upper_bound 找出操作时间晚于当前列的蓝行数量剩下的蓝行就是列先刷、行后刷的情况。循环里 cnt 表示交叉点仍为蓝色的个数blueRows - cnt 就是交叉点为红色的个数从 ans 里减掉正好修正多算的部分。4.3 为什么不能直接从后往前模拟以及时间戳的必要性有同学会想既然只有最后一次操作有效那我从后往前把操作过一遍遇到行就标记这一行最终颜色遇到列就标记这一列最终颜色不也很快吗这个方法能算出蓝行、蓝列的数量但算不出交叉点的归属。因为交叉点的颜色取决于行和列哪个操作发生得更晚而「从后往前遍历」时你会先看到较晚的操作但不知道它对应的行或列另一个维度更晚的操作到底在哪。所以必须显式记录时间戳。这也是这题和「统计人口」共用前缀和思维的差异点——前缀和是空间换时间时间戳是为了处理二维交叉关系的优先级。调试这道题时可以用一个超小的数据比如 2×2 的网格做手工验证把 line 的代码跑一遍对比手工推演的结果。这个习惯能帮你发现到底是计数公式错了还是时间戳比较逻辑错了。5. 四道题通用避坑与排查目录结构、IO 性能与边界条件的实战记录5.1 源文件放错目录整题直接零分现象程序在本地运行完全正确样例全过但提交成绩是 0 分。原因竞赛要求选手按题目英文名建立子目录把源程序放在对应目录下再把整个选手目录放到指定盘符的根目录中。比如题目有 cashier、dune、manhattan 三题选手的目录结构必须是 选手号/cashier/cashier.c、选手号/dune/dune.pas、选手号/manhattan/manhattan.cpp。任何一级目录名拼错、源文件名和题目要求不一致、把 .cpp 文件直接放在选手根目录下评测系统就找不到源文件。解决比赛开始前先建好所有题目目录和源文件每写一题就另存为到对应目录交卷前用文件管理器逐项核对一个字符都不能差。5.2 scanf/printf 和 cin/cout 的性能差距被低估现象统计人口和粉刷匠两题在本地小数据测试秒出结果一到全量数据就超时。原因这两题的数据量都到 5×10^4 和 10^6 级别。cin/cout 默认与 C 标准 IO 同步每次输入输出都要做流同步开销可能相差 5 到 10 倍。粉刷匠要读 10^6 行、每行 3 个数用 cin 不开优化基本必死。解决要么直接用 scanf/printf要么在 main 开头加一行 ios::sync_with_stdio(false)。我一般直接选前者——竞赛环境里 scanf/printf 是最稳的不存在忘关同步的问题。5.3 好朋友的边界x1、xn、Pi0 与 Pim 的不同处理现象样例全过但一提交就 WA 一半测试点。原因漏了某些边界条件。x 在最左边时向左循环根本不存在x 在最右边时向右循环不存在。Pi0 表示不可卖必须跳过Pim 表示买不起也必须跳过。很多人只判断 Pim忘了 Pi0 也要排除或者反过来只排除 0 忘了价格上限。解决把两个方向的搜索条件都写成 p[i] ! 0 p[i] m并且用 break 配合 ans 初始化的方式保证两侧都找过。这道题 n 小哪怕多几个 if 也不影响性能但条件判断的完整性直接决定正确性。5.4 卫星题的「已接收卫星不计数但还占位置」到底怎么理解现象按自己的理解写模拟n5 的样例能过n13 就输出错乱。原因把已接收卫星当成「从环上移除」来写和「跳过但不计数」是两种完全不同的逻辑。如果已接收卫星直接消失间隔计数会跳得更快最终排列对不上题目定义。解决用一个 used 数组标记位置是否被占用数间隔时遇到 used 直接跨过但不增加计数。想验证理解是否正确就手动模拟一遍 n5 的完整过程走一遍题目给的例子你就知道那个「不计算在间隔数量中」意味着什么。5.5 粉刷匠交叉点的重复计数不是简单的「减一次交集」现象用 blueRowsm blueColsn - 蓝行蓝列交集数结果还是不对。原因交叉点不是算一次或减一次那么简单——交叉点的最终颜色取决于该行和该列最后一次操作谁更晚。如果列后刷且列是红色那这个交叉点是红的粗算和修正都必须把它排除如果行后刷且行是蓝色那交叉点是蓝的粗算里算了两次减一次即可。解决必须带上时间戳比较。我给的方法是对蓝色行的时间排序对每个蓝色列二分查找晚于它的行数修正量是精确的。不排序直接两两比较蓝行和蓝列数量到 10^6 就炸了。6. 把复赛题变成训练工具两个变式改造与一个验证习惯一份试题榨干它的价值不只是把四道题 AC 就完事。我一般会做两件事一是改数据范围看旧解法还成不成立二是手工构造一个超小样例来验证算法的每一步。比如好朋友这题把 n 从 100 改到 100000同时把 m 变成一个较大的数原本双向线性枚举 O(n) 的两趟扫描仍然是线性的完全能扛住但如果把题目改成多组查询——每次给一个不同的 x 问最近可买距离——那你就得预处理每个位置左右最近的合法房子或者对价格做某种前缀最值。这个变式能把「单点查询」升级成「区间查询」的思维和统计人口的前缀和形成呼应。粉刷匠的变式更有意思把颜色从红蓝两种改成红蓝黄三种。粗算公式就从 蓝行×m 蓝列×n 变成了三种颜色各自的统计交叉点的修正也要按三种颜色分别处理。你很快会发现时间戳排序 二分的方法完全不依赖颜色数量只要把每个颜色的行列分开统计就行。这比多刷十道同类题更能建立「方法可迁移」的感觉。验证习惯方面我强烈建议每道题写完之后用最笨的暴力法写一个对拍脚本。拿统计人口举例n 取 20m 取 20暴力每次查询遍历区间求和和你的前缀和答案逐行比对随机生成 1000 组数据跑一遍。这个方法是我当年从某位教练那里学来的从那以后我每写一道题都强制自己走一遍「小数据对拍」的流程哪怕只是脑内模拟一遍样例加一个边界用例。竞赛里最贵的是罚时而罚时多半来自你以为对了、其实边界漏了的代码。这份试题四道题覆盖的算法都不算深但每一道都藏了一两个这种「不说破就想不到」的细节能把这些坑提前踩一遍等上了真正的赛场你就比别人少流一次汗。希望帮到你。本文还有配套的精品资源点击获取