简介：第18届绍兴市少儿信息学竞赛复赛试题已整理为一份Word文档，面向小学阶段的信息学爱好者与编程初学者，既可用于备赛练习，也可作为课堂或社团的测评资料。卷面包含“好朋友”“统计人口”“卫星”“粉刷匠”四道经典题目，覆盖变量与数据类型、控制结构、数组与链表、算法设计等核心知识点；每道题均提供了输入输出样例、数据范围说明，部分题目还配有样例解释，文档中另给出比赛目录结构示例和答题注意事项，能帮助读者完整还原竞赛环境、理解命题风格与常见解题策略。资源共1个docx文件，压缩包约32KB，轻量便携，下载后可直接打开使用。目前已有812人浏览学习。通过这份试题，读者可系统检验编程语言应用能力，提升数据结构与算法实战水平，尤其适合准备少儿信息学竞赛或入门NOIP方向的小学生及指导教师参考。
1. 一份少儿信息学复赛试题，为什么值得你花一个下午拆一遍
很多刚入门信息学竞赛的孩子，刷了几十道基础题之后会陷入一个尴尬期：单点知识点都见过，一碰到 NOIP 风格的完整赛题就不知道从哪下手。这份第18届绍兴市少儿信息学竞赛复赛试题，恰好是这种尴尬期的绝佳解药。四道题从线性枚举、前缀和到约瑟夫环变体和百万级网格覆盖计数，难度梯度拉得很开，既有新手能拿满分的送分题，也有需要绕开思维陷阱才能 AC 的压轴题。对小学阶段学编程的人来说，它是一份能真实检验「能不能从会语法进化到会做题」的试金石；对带竞赛的老师来说，它又是现成的模拟赛题源。我把它逐题拆了一遍，每一题的思路、代码、复杂度边界和踩坑点都放在下文，照着复现一遍，比闷头刷十道同类题都管用。
2. 好朋友与统计人口：两道基础题的暴力解法与前缀和优化
2.1 好朋友：双向线性枚举，先想清楚“最近”怎么定义
这道题的核心约束很小：n 最大只有 100，Pi 是非负整数，Pi=0 表示不可卖，且买家资金为 m。换句话说，你要在小 A 家房号 x 的左边和右边分别找「距离最近、价格不超过 m、且 Pi 不为 0」的房子，然后取两侧里更近的那个距离。最容易翻车的写法是只往一边找，或者忘了排除 Pi=0 的房子。
#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 中 x=2，买到 4 号房，输出 20，即 (4-2)×10。所以代码里最后应该输出 ans×10。上面这段为了聚焦距离比较逻辑，先算的是房号差，真正提交前记得在 printf 里乘上 10。这种细节就是竞赛里常见的「样例能过、全盘 WA 」的元凶之一，后面避坑章节还会专门说。
2.2 统计人口：前缀和数组把每次查询压成 O(1)
第二题的数据范围直接从 100 跳到 50000，m 次查询也到了 50000。如果沿用暴力的思路，每次查询都遍历一遍 x 到 y 累加，最坏情况是 50000×50000=2.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 到了 50000，O(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 指向第 step+1 颗未接收卫星，也就是本轮要放置的位置 // 但因为循环里多走了一步，需要回退到真正的目标位置 // 下面处理：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-1，step 就是题目里的「间隔数量」。内层循环模拟从当前位置 cur 出发，沿着环数「未接收的卫星」，数到第 step 颗时停下。这里有个细节：内层 while 循环的条件是 skipped < step，也就是循环体里数到第 step 颗未接收卫星之后，pos 还会继续向后移动一格，指向下一颗卫星的位置。所以循环结束后，pos 实际上站在「第 step 颗被跳过的卫星的下一个位置」，这时候需要从 pos 开始，往后找到第一个空位，才是真正要放置卫星的位置——也就是「第 step+1 颗未接收卫星」。
用样例 n=5 验证：ring[0]=1，cur=0。step=1 时，从位置 1 开始数，跳过 1 颗未接收卫星（位置 1 的 3），pos 停到位置 2，位置 2 是空的，放 2 号卫星。step=2 时，从位置 3 开始，跳过位置 3（5）和位置 4（4），pos 绕回位置 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 是构造不出来的，比如 n=2 就没办法：1 号放位置 0，step=1 时从位置 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::vector<int> 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 好朋友的边界：x=1、x=n、Pi=0 与 Pi>m 的不同处理
现象：样例全过，但一提交就 WA 一半测试点。原因：漏了某些边界条件。x 在最左边时，向左循环根本不存在；x 在最右边时，向右循环不存在。Pi=0 表示不可卖，必须跳过；Pi>m 表示买不起，也必须跳过。很多人只判断 Pi<=m，忘了 Pi=0 也要排除，或者反过来只排除 0 忘了价格上限。解决：把两个方向的搜索条件都写成 p[i] != 0 && p[i] <= m，并且用 break 配合 ans 初始化的方式保证两侧都找过。这道题 n 小，哪怕多几个 if 也不影响性能，但条件判断的完整性直接决定正确性。
5.4 卫星题的「已接收卫星不计数但还占位置」到底怎么理解
现象：按自己的理解写模拟，n=5 的样例能过，n=13 就输出错乱。原因：把已接收卫星当成「从环上移除」来写，和「跳过但不计数」是两种完全不同的逻辑。如果已接收卫星直接消失，间隔计数会跳得更快，最终排列对不上题目定义。解决：用一个 used 数组标记位置是否被占用，数间隔时遇到 used 直接跨过，但不增加计数。想验证理解是否正确，就手动模拟一遍 n=5 的完整过程，走一遍题目给的例子你就知道那个「不计算在间隔数量中」意味着什么。
5.5 粉刷匠交叉点的重复计数不是简单的「减一次交集」
现象：用 blueRowsm + blueColsn - 蓝行蓝列交集数，结果还是不对。原因：交叉点不是算一次或减一次那么简单——交叉点的最终颜色取决于该行和该列最后一次操作谁更晚。如果列后刷且列是红色，那这个交叉点是红的，粗算和修正都必须把它排除；如果行后刷且行是蓝色，那交叉点是蓝的，粗算里算了两次，减一次即可。解决：必须带上时间戳比较。我给的方法是对蓝色行的时间排序，对每个蓝色列二分查找晚于它的行数，修正量是精确的。不排序直接两两比较，蓝行和蓝列数量到 10^6 就炸了。
6. 把复赛题变成训练工具：两个变式改造与一个验证习惯
一份试题榨干它的价值，不只是把四道题 AC 就完事。我一般会做两件事：一是改数据范围看旧解法还成不成立，二是手工构造一个超小样例来验证算法的每一步。比如好朋友这题，把 n 从 100 改到 100000，同时把 m 变成一个较大的数，原本双向线性枚举 O(n) 的两趟扫描仍然是线性的，完全能扛住；但如果把题目改成多组查询——每次给一个不同的 x 问最近可买距离——那你就得预处理每个位置左右最近的合法房子，或者对价格做某种前缀最值。这个变式能把「单点查询」升级成「区间查询」的思维，和统计人口的前缀和形成呼应。
粉刷匠的变式更有意思：把颜色从红蓝两种改成红蓝黄三种。粗算公式就从 蓝行×m + 蓝列×n 变成了三种颜色各自的统计，交叉点的修正也要按三种颜色分别处理。你很快会发现，时间戳排序 + 二分的方法完全不依赖颜色数量，只要把每个颜色的行列分开统计就行。这比多刷十道同类题更能建立「方法可迁移」的感觉。
验证习惯方面，我强烈建议每道题写完之后，用最笨的暴力法写一个对拍脚本。拿统计人口举例：n 取 20，m 取 20，暴力每次查询遍历区间求和，和你的前缀和答案逐行比对，随机生成 1000 组数据跑一遍。这个方法是我当年从某位教练那里学来的，从那以后我每写一道题都强制自己走一遍「小数据对拍」的流程，哪怕只是脑内模拟一遍样例加一个边界用例。竞赛里最贵的是罚时，而罚时多半来自你以为对了、其实边界漏了的代码。这份试题四道题覆盖的算法都不算深，但每一道都藏了一两个这种「不说破就想不到」的细节，能把这些坑提前踩一遍，等上了真正的赛场，你就比别人少流一次汗。希望帮到你。
本文还有配套的精品资源，点击获取
