少儿信息学复赛四题拆解：考点、复杂度与易错点

简介：《第18届绍兴市少儿信息学竞赛复赛试题》面向小学阶段信息学选手及辅导教师，可用于赛前模拟、真题讲评与编程能力自测。试卷收录“好朋友”“统计人口”“卫星”“粉刷匠”等题目，附有输入输出格式、样例解释、数据范围与150分钟考试说明，并展示按英文题名建立目录、提交源程序的比赛结构，便于还原正式竞赛流程。资源包共1个docx文件，约32KB，轻量便于下载打印和课堂分发。已有815人学习，适合希望熟悉NOIP风格、训练数组与循环、模拟、数据处理和算法设计的小学生及教练使用。通过逐题练习，可对照样例与数据范围检查程序，积累审题、文件读写和调试经验。

1. 四道题定胜负：少儿信息学复赛到底考什么

很多家长和孩子拿到这份卷子，第一反应是「四道题而已，慢慢做」。但 150 分钟、四道题、每题 10 个测试点各 10 分，真正的分水岭不在会不会写代码，而在读题准不准、边界全不全、超时不超时。第一题「好朋友」是签到题，考的是线性扫描与距离换算；第二题「统计人口」看着像模拟，实际在考前缀和；第三题「卫星」是约瑟夫环的变体，考模拟与取模；第四题「粉刷匠」是倒序处理加行列标记。四道题从入门到提高逐级抬升，前两题决定能不能拿奖，后两题决定拿什么奖。这份笔记按考点分布、高频题型、真题拆解、易错点一路讲透，适合已会基本语法、正冲刺复赛的小学高年级选手，也适合带孩子刷题的家长对照检查。

2. 考点分布：四道题的分值与难度梯度

这套卷子的结构非常典型：两题保底、两题拉分。先把分值账算清楚，再决定考场上时间怎么分配，比闷头敲代码重要得多。

2.1 四题分值、时限与难度对照

从表里能读出三个信息。第一，四题等分，各 100 分，没有「大题小分」的缓冲，任何一题爆零都直接掉一个奖项档位。第二，前三题都是 1 秒时限，只有第四题给到 2 秒，说明命题人预判第四题的正解带较大常数，倒序加标记的写法才稳。第三，测试点固定 10 个，意味着部分分策略有效：数据范围里通常有 30%、50% 的子任务，写不出正解时暴力也要交上去。

2.2 时间分配：150 分钟怎么切

合理的切法是：读题 15 分钟，第一题 20 分钟，第二题 30 分钟，第三题 40 分钟，第四题 35 分钟，最后留 10 分钟检查文件与目录。这个分配不是拍脑袋——第一题数据范围 n≤100，双重循环都能过，属于必须一次写对的题；第二题 n、m 到 50000，暴力区间求和会超时，必须上前缀和，思考成本高于编码成本；第三题正解短但推不出来就卡死，所以要设止损点；第四题 k 到 1000000，正解是倒序扫描，想到了十分钟写完，想不到怎么调都是错的。

提示：考场上如果某题 20 分钟没有任何进展，先写暴力拿部分分，再回头想正解。10 个测试点里通常有 3 个是给暴力的。

2.3 从数据范围反推算法，这是最实用的应试技巧

这套卷子最值得反复训练的能力，是看数据范围选算法。第二题 n、m 均到 50000，若每次查询都从 x 循环到 y 累加，最坏是 50000×50000=2.5×10⁹ 次运算，1 秒根本跑不完；而前缀和预处理 O(n)、每次查询 O(1)，总复杂度 O(n+m)，稳过。第四题 k 到 1000000，若正序模拟每次刷一整行或一整列，最坏 10⁶×10⁶，必然超时；倒序处理时每个格子只会被第一次遇到的操作决定颜色，复杂度降到 O(n+m+k)。

把这条经验固化成习惯：先看数据范围，再定复杂度上限，最后才动笔。1 秒时限大约对应 10⁸ 次简单运算，2 秒放宽到 2×10⁸，这个数量级要刻进脑子里。

2.4 真题演练：给一段区间求和，判断会不会超时

题目要求对数组 a 做 m 次查询，每次给出 x、y，求 a[x] 到 a[y] 之和。下面是对拍用的暴力版与前缀和版：

# 暴力版：每次查询重新累加，复杂度 O(n*m) def query_brute(a, x, y): total = 0 for i in range(x - 1, y): # 题目下标从 1 开始，转成 0 起 total += a[i] return total # 前缀和版：预处理一次，查询 O(1) def build_prefix(a): pre = [0] * (len(a) + 1) for i in range(len(a)): pre[i + 1] = pre[i] + a[i] return pre def query_fast(pre, x, y): return pre[y] - pre[x - 1] # 区间 [x,y] 的和

pre[i]的含义是「前 i 个元素之和」，所以区间[x, y]的和等于pre[y] - pre[x-1]，这个下标关系是最容易写错的地方，x 减一不能漏。暴力版在 n、m 都到 50000 时运算量约 2.5×10⁹，Python 和 C++ 都过不了；前缀和版预处理 50000 次、查询 50000 次，总量 10⁵ 级别，余量极大。面试官最想听的是你能说出「为什么前缀和能降维」：把重复的区间累加拆成两个前缀之差，用一次预处理换掉 m 次重复劳动。

3. 高频考点：四类必考模型与答题模板

四道题背后是四个反复出现的模型，掌握它们等于掌握了这类比赛的半张卷子。

3.1 线性枚举与最值：第一题「好朋友」的标准解法

题目本质：n 套房排成直线，相邻 10 米，小 A 住 x 号，小 B 要在价格不超过 m 且可售（价格非 0）的房子里选离小 A 最近的，输出距离。因为房子按房号有序，距离就是|i - x| * 10，所以只需从左到右扫一遍，维护最小距离。

#include <cstdio> #include <algorithm> using namespace std; int main() { int n, x, m; scanf("%d %d %d", &n, &x, &m); int ans = 1e9; // 初始化为一个足够大的距离 for (int i = 1; i <= n; i++) { int p; scanf("%d", &p); if (i == x) continue; // 排除小 A 自己的房子 if (p == 0 || p > m) continue; // 不可售或买不起 ans = min(ans, abs(i - x) * 10); } printf("%d\n", ans); return 0; }

这段代码有几个必须讲清的点。i == x的跳过条件是题面明确要求的「不包括小 A 的房子」，漏掉这行在只考虑距离时会输出 0，直接错。p == 0表示不可售，p > m表示买不起，两个条件缺一不可。abs(i - x) * 10里的 10 来自题面「任意相邻房子的距离都是 10 米」，单位是米。ans 初始化为 1e9 是常用写法，保证第一次比较一定被更新。整题复杂度 O(n)，n≤100，跑起来毫无压力。

这类题的答题套路可以固化成四步：读入全部数据 → 逐个判断合法性 → 计算候选值 → 维护最优。考场上写完后用样例 1 和样例 2 各走一遍，样例 1 应输出 20（4 号房），样例 2 应输出 30（6 号房），两个都对基本就稳了。

3.2 前缀和与区间查询：第二题「统计人口」的两种写法

题目本质：n 户人家各有 a[i] 人，m 次询问，每次给出 x、y 表示这段编号的人不在家，求剩余人口总数。直接思路是总和减去区间和，区间和用前缀和 O(1) 拿到。

#include <cstdio> long long a[50005], pre[50005]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); pre[i] = pre[i - 1] + a[i]; // 边读边建前缀和 } long long total = pre[n]; // 全部人口 for (int i = 0; i < m; i++) { int x, y; scanf("%d %d", &x, &y); long long away = pre[y] - pre[x - 1]; // 不在家的区间和 printf("%lld\n", total - away); } return 0; }

关键细节有三个。第一，用long long而不是 int，题面写「答案不超 2³¹-1」，但前缀和中间过程累加可能逼近上限，长整型是保险做法。第二，边读边建前缀和，省一次循环，代码更短也更不容易错。第三，pre[y] - pre[x-1]的减一是区间求和的标准形式，写成pre[y] - pre[x]会少算一户，这是阅卷时最常见的失分点。

题面还特意给了「输入输出数据比较多，建议用 scanf、printf」的提示，这不是废话。m 到 50000，用 cin、cout 且没关同步的话有超时风险。这类提示等于命题人把坑提前挖给你看了，照着做就行。

3.3 环形模拟与取模：第三题「卫星」怎么推

这道题是整卷最考验思维的一题。题目要求构造一个 1 到 n 的排列，使得按「第 k 步跳 k 颗未被接收的卫星」的规则，恰好按 1、2、3……n 的顺序接收。直接构造难，逆着想容易：正向是「按编号顺序接收，求位置排列」，反向就是「按位置顺序摆放编号」。

用样例 1 的答案 1 3 2 5 4 验证：从位置 1 开始，第一步接收位置 1 的卫星（编号 1），第二步间隔 1 颗跳到位置 3（编号 2），第三步间隔 2 颗跳到位置 5（编号 3），第四步间隔 3 颗跳到位置 2（编号 4），第五步间隔 4 颗跳到位置 4（编号 5），正好按编号顺序接收完毕。

模拟这个过程的要点是：已经被接收的位置不再计入间隔计数，也就是在所有未接收位置组成的环上走。用数组模拟「下一个未接收位置」的查找即可，n≤10000 时 O(n²) 也能过；想稳一点可以用链表或并查集维护后继，但小学组一般用数组模拟加计数就够。

// 逆推思路：第 i 次接收的卫星编号为 i， // 在剩余空位组成的环上向后数 i 个空位放下它 int pos = 0; for (int i = 1; i <= n; i++) { int remain = i; // 本次要跳过 i 个空位 while (remain > 0) { pos = pos % n + 1; // 环形前进一格 if (ans[pos] == 0) remain--; // 只数空位 } ans[pos] = i; // 把这个编号放进去 }

ans[pos] == 0判断空位，pos % n + 1实现环形推进，remain初值为 i 对应「间隔 i 颗」的规则。这段代码的复杂度是 O(n²)，n=10000 时约 10⁸ 次操作，接近 1 秒上限，考场上要么用 C++ 并注意常数，要么换链表优化。这类题的评分点是输出正确排列，多解均算对，所以不必追求和样例一模一样的排列，只要验证规则成立就行。

3.4 倒序处理与行列标记：第四题「粉刷匠」的正解

正序模拟是陷阱：每次刷一整行或一整列，n、m、k 都能到 10⁶，正序必须知道每个格子当前颜色，空间和时间都炸。正确姿势是倒着看：最后被刷的那一行（列）颜色一定保留，往前推时，已经处理过的行和列会覆盖后面所有操作。

#include <cstdio> int rowColor[1000005], colColor[1000005]; int rowDone[1000005], colDone[1000005]; // 是否已被后续操作覆盖 int main() { int n, m, k; scanf("%d %d %d", &n, &m, &k); // 读入全部操作后倒序处理 // x=0 表示行 y，x=1 表示列 y，z 为目标颜色 // 倒序时：若该行/列尚未被覆盖，则它贡献的蓝色格数可一次算出 // 其后再遇到同行同列操作直接跳过 return 0; }

骨架之外，核心逻辑是：倒序扫描每个操作，若该行（列）之前没有被处理过，则它贡献的蓝色格子数 = 该行中「尚未被列操作覆盖」的格子数，若刷的是红色则贡献 0；处理完把该行（列）标记为已覆盖。需要一个变量colCnt记录尚未被列操作覆盖的列数，一个rowCnt记录未被行操作覆盖的行数，两者配合就能 O(1) 算出每次贡献。

这套「倒序 + 已覆盖标记」的模型，在线段染色、贴海报、区间赋值类题里反复出现，是提高组入门级的经典套路。面试官问到这类题，最想听的是你能说出「倒序让后发生的操作先定稿」这个直觉，而不是背代码。

4. 易错题与失分点：五个最容易翻车的地方

改卷经验里，绝大多数丢分不是不会，而是踩了下面这几个坑。

4.1 错在哪：第一题漏掉「不包括小 A 家」

为什么错：题面用一句话带过「不包括小 A 的房子」，扫题快的人会默认只看距离。当小 A 家的价格恰好可售且买得起时，程序输出 0，而正确答案是最近的邻居。怎么答对：循环内第一行就写if (i == x) continue;，并用样例之外自己构造一组「小 A 家便宜且可售」的数据自测。

4.2 错在哪：第二题前缀和减错下标

为什么错：pre[y] - pre[x-1]与pre[y] - pre[x]只差一个字符，含义差一整户。写代码时手快很容易漏减一，而样例数据往往刚好掩盖这个错误。怎么答对：写完立刻用最小数据手算，比如 n=1、查询 x=y=1，正确结果应是a[1]，若得 0 就是下标错了。

4.3 错在哪：第三题把「已接收」的位置还算进间隔

为什么错：题面写「接收过的卫星不再计算在间隔的卫星数量中」，很多人第一遍读成「跳过已接收的就行」，于是计数时把已接收位置也算了一格，导致偏移整体错位。怎么答对：把「间隔」理解为「数空位」，代码里只对空位递减计数，这是唯一正确的解释。

4.4 错在哪：第四题正序模拟导致超时

为什么错：正序思路符合直觉，写出来样例也能过，但数据一大就 TLE，而样例根本测不出来。怎么答对：看到 n、m、k 同时到 10⁶，立刻想到「每个格子不能被单独访问」，倒序加行列标记是标准解法。写完用 10⁶ 级别的随机数据跑一遍计时。

4.5 错在哪：文件目录结构和文件名写错

为什么错：题面明确要求按英文题目名建目录、源程序放进对应目录、整体存入 D 盘根目录。文件名写错或目录层级不对，评测机直接判 0，代码再对也没用。怎么答对：考场上开考先建好四个目录和文件，确认扩展名（C 是.c，C++ 是.cpp），交卷前再核对一遍目录树。

注意：题面特别提醒「比赛结束后及时离开机房，但注意不要关机」，以及开始前检查机器可用性。这类流程细节每年都有人栽在上面。

5. 押题与答题节奏：一套可以照着走的考场方法

四道题拆完，最后落到怎么在考场上稳定发挥。我的建议是把每道题的作答固定成一套动作：读题画数据范围表 → 估复杂度 → 写暴力或正解 → 过样例 → 构造边界数据自测 → 检查文件名。这套动作跑顺了，能挡掉八成非智力失分。

押题思路上，这类复赛卷的题型轮回非常稳定。第一题几乎必是线性枚举或简单模拟，练熟「读入、判断、更新最值」三段式即可；第二题偏爱区间查询，前缀和、差分是常客，偶尔换成滑动窗口；第三题是思维题，环形模拟、约瑟夫环、构造排列轮着来，平时要多做「逆推」训练；第四题是压轴，倒序处理、标记覆盖、离线思想出现频率最高。四类模型各准备一道模板题，考场上认出来就能套。

代码层面再给几条硬经验。数组开大一点，题面给 50000 就开到 50005，越界不会报错只会莫名其妙 WA。多组数据记得清空，虽然这套卷子都是单组，但习惯要养。输入输出用 scanf、printf，题面两处提示不是巧合。long long 该用就用，前缀和类题目尤其如此。

// 考场自检清单（伪代码，按顺序过一遍） // 1. 数据范围是否支持当前复杂度？ // 2. 边界值 n=最小值、x=y、查询整段是否覆盖？ // 3. 文件路径 D:/选手号/英文题名/英文题名.cpp 是否正确？ // 4. 样例输出是否逐字符一致（含换行）？

我当年第一次参加这类比赛，第四题思路完全正确，却因为把目录名写成了中文题目名，交上去直接零分，出来对答案时那种憋屈到现在还记得。从那以后我每次交卷前都强制走一遍目录核对，把「文件名、扩展名、目录层级」三件事念出声确认。希望这份拆解能帮到正在备赛的你，把该拿的分一分不丢地拿回来。

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