少儿信息学复赛四道题解析：枚举、前缀和、模拟与逆向思维

简介：这份资源是第18届绍兴市少儿信息学竞赛复赛试题文档，面向备战NOIP系列赛事的小学高年级及初中低年级选手与信息学教练，可用于赛前模拟训练与算法专题查漏补缺。压缩包内共1个docx文件，约32KB，完整收录四道赛题：好朋友、统计人口、卫星与粉刷匠，每题均给出问题描述、输入输出格式、样例及数据范围，并附比赛目录结构示例与提交规范提醒。题目覆盖数组与循环、前缀和与区间统计、环形模拟、行列染色等知识点，难度梯度清晰，适合按题拆解练习。该资源已有815人学习下载，读者可据此还原真实赛场题型分布，训练读题、建模与边界处理能力，也可作为教练组卷与课堂讲评的素材。

1. 从四道题看这场复赛到底考什么

先看一个反直觉的失分点：这场复赛四道题，每道题 10 个测试点、每点 10 分，满分 400，但真正拉开差距的往往不是最后一题，而是第一题。为什么？因为第一题“好朋友”逻辑极简，却埋了“距离最近优先、价格其次”的双条件筛选，很多选手扫一眼就动手，结果样例 2 直接翻车。少儿信息学竞赛复赛的定位很清晰：不考高深算法，考的是把题意读准、把边界想全、把输入输出格式抠死。150 分钟、四道题、每题 1 秒时限（粉刷匠 2 秒），这个配置决定了它是一场“稳者胜”的比赛，而不是“谁会高级数据结构谁赢”。适合已经能写循环、数组、简单模拟，但还没系统练过真题的小学高年级选手。这份试题的价值就在于：它把复赛最常考的四类模型——枚举筛选、区间求和、模拟构造、逆向统计——一次性摆在你面前，照着练一遍，比刷十套来路不明的题都管用。

2. 高频考点拆解：四道题对应四种必练模型

2.1 好朋友：双条件枚举与“最近优先”的排序陷阱

这道题的题意翻译成大白话：一条直线上 n 个房子，间距固定 10 米，小 A 住 x 号，小 B 要买一套不是 x 号、价格不超过 m 的房子，问最近能近到多少米。关键约束是“在两家距离最近的前提下”求距离，也就是说价格只是过滤条件，距离才是优化目标。

最稳的写法是枚举所有房号，跳过 x 号、跳过价格为 0 的、跳过价格大于 m 的，对剩下的算距离取最小值。因为 n ≤ 100，O(n) 枚举完全够用，不需要任何花哨技巧。但这里有个血泪经验：不少选手会先按价格排序再找最近的，这就把“最近优先”理解反了。正确顺序是先筛可买、再比距离。

n, x, m = map(int, input().split()) prices = list(map(int, input().split())) best = float('inf') for i in range(n): house = i + 1 # 房号从 1 开始 if house == x: # 不能买小A自己的房子 continue if prices[i] == 0: # 0 表示不可卖 continue if prices[i] > m: # 超出预算 continue dist = abs(house - x) * 10 if dist < best: best = dist print(best)

这段代码的核心在三个continue：它们分别对应题目里三个“不合法”条件，顺序无所谓，但一个都不能漏。abs(house - x) * 10是距离计算，乘 10 是因为相邻房距 10 米。参数上唯一要小心的是best的初值，用float('inf')比用一个大整数更安全，避免 n 很小时初值本身成为答案。如果题目保证一定有解，最后直接输出best即可；若担心无解，可加一个判断，但本题数据范围下不必过度设计。

2.2 统计人口：前缀和是区间求和的唯一正解

第二题的数据范围是 n、m 都到 50000，如果每次查询都从 x 循环到 y 累加，最坏情况 50000 × 50000，必然超时。这类“多次区间求和”的题，复赛里出现频率极高，标准解法就是前缀和：预处理一个pre[i] = a[1] + ... + a[i]，那么区间 [x, y] 的和就是pre[y] - pre[x-1]，单次查询 O(1)。

题目问的是“x 到 y 不在家时能核查多少人口”，等价于总人口减去区间 [x, y] 的人口。所以答案就是total - (pre[y] - pre[x-1])。

#include <cstdio> int a[50005]; long long pre[50005]; // 前缀和可能超 int，用 long long 稳 int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); pre[i] = pre[i-1] + a[i]; // 边读边建前缀和 } long long total = pre[n]; while (m--) { 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，虽然题目说答案不超 2^31-1，但中间累加过程在极端数据下可能逼近上限，用 long long 是后悔药。第二，题目明确提示“输入输出数据比较多，建议用 scanf、printf”，这不是客套话，50000 行输出用 cin/cout 且没关同步的话，1 秒时限下很可能翻车。pre[x-1]的下标从 1 开始设计，正好避开 x=1 时越界的问题，这是前缀和的标准写法，值得形成肌肉记忆。

2.3 卫星：环形模拟与“已接收不计数”的构造逻辑

第三题是四道里思维难度最高的。题意是：n 颗卫星排成一个环，你要设计一个排列，使得按“先收 1 号，然后间隔 1 颗收 2 号，再间隔 2 颗收 3 号……”的规则，恰好按 1 到 n 的顺序收完所有卫星。注意规则里那句“接收过的卫星不再接收第二次信号，即此卫星不计算在间隔的卫星数量中”——这是整道题的题眼，也是最多人读漏的一句。

理解方式：把还没被接收的卫星看成一个动态缩小的环，每次从当前位置出发，数“间隔数 + 1”个未接收的卫星，落点就是下一颗要收的卫星。题目要求输出的是卫星的初始排列，使得这个接收顺序恰好是 1, 2, 3, …, n。换句话说，我们要反推：第 k 步接收的卫星编号是 k，它在环上的位置由前面的间隔规则决定。

一种可行的构造思路是正向模拟“空位”：维护一个长度为 n 的环，初始全空，第 1 步把 1 放在位置 1；第 k 步时，从上一颗的位置出发，在空位中数 k 个（因为间隔数为 k-1，加上落点本身共 k 个空位），把 k 放在那里。最后按环顺序输出每个位置上放的编号。

#include <cstdio> int pos[10005]; // pos[i] 表示第 i 个位置放的卫星编号 bool used[10005]; int main() { int n; scanf("%d", &n); int cur = 0; // 当前位置（0 基） for (int k = 1; k <= n; k++) { int step = k; // 第 k 步需要走过 k 个空位 while (step > 0) { cur = (cur + 1) % n; if (!used[cur]) step--; // 只数空位 } used[cur] = true; pos[cur] = k; } for (int i = 0; i < n; i++) printf("%d ", pos[i]); return 0; }

这段代码的关键在while循环里：cur每次前进一步，只有遇到空位才step--，这样“已占位置不计数”的规则就被自然实现了。step = k而不是k-1，是因为间隔 k-1 颗加上落点本身，正好走过 k 个空位。n ≤ 10000 时这个 O(n²) 的模拟在 1 秒内可以跑完，但如果数据再大就要考虑用树状数组优化，复赛阶段先保证正确性。输出样例 1 的1 3 2 5 4可以用这段逻辑手工验证一遍，验证通了，这类环形构造题就有了底。

2.4 粉刷匠：逆向扫描，最后一次操作决定颜色

第四题的数据规模到 10^6，正向模拟每次刷一整行或一整列，最坏 10^12 次格子操作，必然超时。这类“多次覆盖、问最终状态”的题，标准套路是逆向思考：最后被刷的那一行或那一列，它的颜色是最终确定的，不会再被覆盖；把它处理掉之后，倒数第二次操作的那一行/列，除了与已处理行列交叉的格子外，其余格子颜色也确定了。

具体做法：从第 k 次操作倒着往前扫，维护哪些行、哪些列已经被“定色”。对于一次刷行操作，如果这一行还没被定色，那么这一行中所有“列未被定色”的格子颜色由此操作决定，蓝色则累加列数减去已定色列数；然后把该行标记为已定色。刷列操作同理。这样每个格子只被统计一次，复杂度 O(k)。

#include <cstdio> bool rowDone[1000005], colDone[1000005]; int op[1000005][3]; int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < k; i++) scanf("%d%d%d", &op[i][0], &op[i][1], &op[i][2]); long long ans = 0; int doneRows = 0, doneCols = 0; for (int i = k - 1; i >= 0; i--) { // 逆序扫描 int type = op[i][0], idx = op[i][1], color = op[i][2]; if (type == 0) { // 刷行 if (rowDone[idx]) continue; rowDone[idx] = true; if (color == 1) ans += m - doneCols; // 该行中列未定色的格子 doneRows++; } else { // 刷列 if (colDone[idx]) continue; colDone[idx] = true; if (color == 1) ans += n - doneRows; doneCols++; } } printf("%lld\n", ans); return 0; }

参数说明：op数组存原始操作序列，rowDone/colDone标记某行某列是否已被更晚的操作覆盖。逆序时遇到已定色的行/列直接跳过，因为它的最终颜色由更晚的操作决定。m - doneCols是这一行里还没被列操作定色的格子数，只有这些格子才真正由本次行操作决定颜色。答案用long long，因为 10^6 × 10^6 的格子数会超 int。这道题是四道里最值得反复练的，因为它把“逆向思维”这个复赛高频套路体现得最干净。

3. 易错点集中营：这五类失分最冤

3.1 文件目录结构没按要求建

错在哪：选手把源程序随便丢在 D 盘根目录，或者目录名用了中文题目名。为什么错：试题明确要求每题建一个与英文题目名同名的目录，源程序放在对应目录下，整体存入 D 盘根目录，且只交源程序。怎么答对：赛前就把friend/、people/、star/、paint/四个空目录建好，源程序文件名也用英文题目名加对应扩展名，交卷前对着目录结构示例逐项核对一遍。

3.2 好朋友题把“最近优先”做成“最便宜优先”

错在哪：先按价格排序，取第一个买得起的房子算距离。为什么错：题目要的是距离最近，价格只是门槛，排序会打乱距离关系，样例 2 就会答错。怎么答对：老老实实枚举所有房号，用距离做比较键，价格只做过滤条件，三个continue一个不漏。

3.3 统计人口题用 cin/cout 且没关同步

错在哪：50000 行输出用默认 cin/cout，1 秒时限下超时。为什么错：题目已经明示“建议用 scanf、printf”，这是出题人给的信号。怎么答对：C++ 选手直接用 scanf/printf，或者至少加ios::sync_with_stdio(false)；同时前缀和数组开 long long，别在累加上限上赌运气。

3.4 卫星题把“间隔数”直接当步长

错在哪：第 k 步只走 k-1 个空位就落点。为什么错：间隔 k-1 颗卫星，加上落点本身，实际要走过 k 个空位，差一位就全盘错。怎么答对：用step = k配合“只数空位”的循环，拿 n=5 的样例手工推一遍，确认输出1 3 2 5 4再提交。

3.5 粉刷匠题正向模拟导致超时

错在哪：每次操作遍历整行或整列改颜色，k 到 10^6 时操作次数爆炸。为什么错：没有识别出“后操作覆盖先操作”的逆向结构。怎么答对：从最后一次操作倒着扫，用行/列定色标记跳过已被覆盖的操作，每个格子只统计一次，答案开 long long。

4. 考场答题节奏：150 分钟怎么分配才不慌

四道题的分值完全均等，每题 100 分，这意味着“保三争四”比“死磕一题”划算得多。我的建议节奏是：开赛后前 10 分钟通读四题，按“好朋友 → 统计人口 → 粉刷匠 → 卫星”的顺序做，前两题控制在 40 分钟内拿下并自测样例，粉刷匠留 40 分钟，卫星留 40 分钟，最后 20 分钟专门做目录结构核对和边界数据自测。

这张表不是让你卡着秒表走，而是提醒你：任何一题卡住超过 20 分钟，先跳过去拿别的题的分。复赛的测试点分值是均摊的，一道题写对 7 个点就是 70 分，比在一道题上从 70 分抠到 100 分容易得多。另外，每道题写完先跑样例，样例不过绝不进入下一题；样例过了再自造一组最小数据和一组边界数据，比如 n=2、x=1、m 刚好等于某房价，这类数据最能暴露下标和过滤条件的漏洞。

最后说一个习惯。我早年带选手时见过太多人栽在“题读了一半就开写”上，后来每次模拟赛我都强制要求先在本子上把每题的输入、输出、过滤条件、数据范围抄一遍再动手，抄完往往自己就发现漏了条件。这份试题的四道题，每一道都值得按这个流程走一遍：先抄题意，再写伪代码，再落代码，最后自测。希望帮到你。

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