简介：这份资源是第18届绍兴市少儿信息学竞赛复赛试题文档，面向备战NOIP及小学阶段信息学竞赛的学生与指导教师，可用于熟悉正式赛制、检验算法与编程基础。试题包含“好朋友”“统计人口”“卫星”“粉刷匠”四道题目，覆盖数组与循环、区间统计、模拟与环状结构、网格染色等知识点，并附有输入输出格式、样例解释与数据范围约定，便于读者按题练习、对照验证与查漏补缺。资源包共1个docx文件，约32KB，内容为完整试题文本，结构清晰，适合直接打印或分题训练。目前已有815人学习下载，可作为赛前模拟与专题突破的参考材料。
1. 从四道题看这场复赛到底考什么
四道题、150 分钟、每题 10 个测试点各 10 分，满分 400。很多家长和孩子一拿到卷子就埋头写代码，结果第一题文件建错目录直接零分，这种翻车每年都有。这场复赛不考偏门算法，考的是三件事：能不能把题意准确翻译成模拟流程、能不能在 1 秒时限内选对数据结构、能不能严格按文件格式交卷。好朋友考的是带约束的枚举，统计人口考前缀和，卫星考约瑟夫环的逆向构造，粉刷匠考倒序处理加行列去重。四道题难度梯度明显，前两题拿满 200 分是及格线，第三题决定能不能进前列，第四题拉开差距。适合已经学过循环、数组、简单递推，正在准备小学组信息学竞赛复赛的学生，也适合带队的指导老师拿来当模拟卷讲评。
2. 好朋友与统计人口：签到题里藏着 200 分的基本盘
这两道题在整卷里属于必须拿满的部分。从历年小学组复赛的得分分布看，前两题全对的人数直接决定能不能拿到二等奖以上，因为后两题区分度太大，靠第三第四题翻盘的风险极高。这一章把两道题的考点拆开讲，每道题给一段可运行的参考实现，再配一道变式练习，目的是让读者看完就能自己写出来、跑过样例。
2.1 好朋友：带约束的最近距离枚举
题目本质很简单：在一条直线上有 n 套房，小 A 住 x 号，小 B 要买一套离小 A 最近且价格不超过 m 的房（价格 0 表示不可卖），求最近距离。相邻房距 10 米，所以距离就是房号差的绝对值乘 10。
数据范围 n ≤ 100，这个规模下完全不需要任何优化，直接枚举每一套房，跳过 x 号本身、跳过价格为 0 的、跳过价格大于 m 的，剩下的取房号差绝对值最小的那个，乘 10 输出即可。很多同学在这里想复杂了，去排序或者用双指针，反而容易在边界上出错。
n, x, m = map(int, input().split()) prices = list(map(int, input().split())) best = float('inf') for i in range(n): house_no = i + 1 if house_no == x: # 不能买小A自己的房子 continue if prices[i] == 0: # 0 表示不可卖 continue if prices[i] > m: # 超出预算 continue dist = abs(house_no - x) * 10 if dist < best: best = dist print(best)这段代码里best初始化为无穷大，保证第一套符合条件的房一定能更新它。循环变量i从 0 开始是因为列表下标从 0 起，而房号从 1 起，所以house_no = i + 1这个转换不能漏。三个continue的顺序无所谓，但一个都不能少——漏掉prices[i] == 0会把不可卖的房算进去，漏掉预算判断会把买不起的房算进去，漏掉house_no == x会输出距离 0。
用样例 1 验证：n=6, x=2, m=600，价格序列 0 80 56 89 0。房号 1 价格 0 跳过，房号 2 是小 A 跳过，房号 3 价格 56 符合，距离 10 米；房号 4 价格 89 符合，距离 20 米；房号 5 价格 0 跳过；房号 6 价格 0 跳过。最近是房号 3，距离 10？但样例输出是 20。这里要仔细看样例解释：样例 1 说小 B 可买的房号为 4 号。为什么 3 号不行？重新读题——价格序列是0 80 56 89 0，对应房号 1 到 5？不对，n=6 应该有 6 个数，但样例只给了 5 个。这是原题数据的一个瑕疵，按 6 套房理解，价格序列应为 6 项。实际考试中如果遇到这种输入项数与 n 不符的情况，以题目描述和样例解释为准，样例解释明确说买 4 号房，距离 20 米，说明 3 号房要么价格超预算要么不可卖。这类细节提醒我们：样例解释比样例数据更可靠，读题时要把样例解释逐字看完。
提示：考试时如果发现输入数据项数和题目描述对不上，先看样例解释怎么说的，按解释的逻辑写代码，不要卡在数据上浪费时间。
变式练习：如果题目改成"在距离最近的前提下，输出能买到的房号最小的那套"，代码只需在距离相等时比较房号即可，把if dist < best改成if dist < best or (dist == best and house_no < best_house)，同时记录best_house。这个改动考的是"多关键字排序"的思维，复赛里经常出现。
2.2 统计人口：前缀和把 O(nm) 压到 O(n+m)
题目给 n 户人家的人口数，m 次询问，每次问编号 x 到 y 的人都不在家时，能核查到多少人口。翻译一下：总人口减去区间 [x, y] 的人口和。
n 和 m 都到 50000，如果每次询问都循环累加 x 到 y，最坏情况 m × n = 2.5 × 10^9 次操作，1 秒时限下必然超时。标准解法是前缀和：预处理一个数组pre[i]表示前 i 户的总人口，那么区间 [x, y] 的和就是pre[y] - pre[x-1]，每次询问 O(1)，总复杂度 O(n + m)。
#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]; // 递推构造前缀和 } for (int i = 0; i < m; i++) { int x, y; scanf("%d%d", &x, &y); long long ans = pre[n] - (pre[y] - pre[x-1]); printf("%lld\n", ans); } return 0; }pre数组用long long是因为题目说答案不超过 2^31-1，但中间累加过程可能溢出 int，保险起见用 64 位。pre[0]默认为 0，这样x=1时pre[x-1]就是pre[0]，不需要特判。输出用%lld对应long long，用%d会输出错误值，这是 C 语言选手最常见的翻车点之一。
题目末尾专门提示"输入输出数据比较多，建议用 scanf、printf"，这不是客套话。50000 行输入用cin在部分老评测机上会慢到超时，用scanf是稳妥选择。如果坚持用cin，至少加ios::sync_with_stdio(false)。
用样例验证：n=4, m=2，人口 3 1 5 6。pre = [0, 3, 4, 9, 15]。第一次询问 1 3，区间和 = pre[3] - pre[0] = 9，总人口 15，答案 6，正确。第二次询问 3 3，区间和 = pre[3] - pre[2] = 5，答案 10，正确。
注意：前缀和的下标从 1 开始最省心，
pre[i]表示前 i 个元素的和，这样区间 [x, y] 的公式统一为pre[y] - pre[x-1]，不需要对 x=1 做特殊处理。
变式练习：如果询问改成"编号 x 到 y 的人在家，其余不在家，求能核查到多少"，答案就变成pre[y] - pre[x-1]本身，逻辑反过来而已。再难一点，如果询问是"编号 x 到 y 的人不在家，但编号 z 的人临时回来了"，就需要在前缀和基础上做单点修正，考的是对前缀和可减性的理解。
3. 卫星：约瑟夫环的逆向构造怎么推
这道题是整卷的分水岭。50% 数据 n ≤ 1000，100% 数据 n ≤ 10000，看起来规模不大，但直接模拟"按规则接收信号"再反推排列，思路不对会绕很久。这一章先讲清楚题目规则的本质，再给构造方法，最后用代码验证。
3.1 把接收规则翻译成"报数出环"
题目描述读起来绕，核心规则是：卫星排成一个环，从 1 号开始接收，之后每次间隔的卫星数量等于上一次接收到的卫星编号。间隔时只数还没被接收的卫星，已经接收过的不计入。要求设计一个排列，使得接收顺序恰好是 1, 2, 3, …, n。
换个角度理解：我们有一个环，按接收顺序依次"取出"卫星。第 1 次取 1 号；第 2 次从 1 号往后数 1 个未取出的，取到 2 号；第 3 次从 2 号往后数 2 个未取出的，取到 3 号；第 k 次从上一个取出的位置往后数 k-1 个未取出的，取到 k 号。注意间隔数和"数几个"差 1：间隔 1 颗意味着往后走 2 步（跳过 1 颗，落到下一颗），间隔 2 颗意味着往后走 3 步。题目里"间隔的卫星数量为上一次接收到的卫星编号"，第 2 次接收时上一次编号是 1，间隔 1 颗，往后走 2 步。
所以构造过程是：维护一个长度为 n 的环，初始时所有位置为空。第 1 步把 1 号卫星放在某个位置（不妨就放在环的起点）。第 k 步（k 从 2 到 n），从上一个放置位置出发，在环上往后数 k 个空位（因为要间隔 k-1 颗已放置的？这里要小心），把 k 号卫星放进去。
更清晰的表述：我们按 1 到 n 的顺序往环里填卫星编号。填第 k 个时，从第 k-1 个的位置出发，往后数 k 个空位（空位就是还没填卫星的位置），把 k 填进去。为什么是 k 个空位？因为接收时第 k 次是"间隔 k-1 颗已接收的卫星"，等价于在剩余未接收的卫星中往后走 k 步。用 n=5 验证：填 1 在位置 0；填 2 时从位置 0 往后数 2 个空位，位置 1 空、位置 2 空，填在位置 2；填 3 时从位置 2 往后数 3 个空位，位置 3、4、0（绕回），填在位置 0？但位置 0 已经有 1 了，空位是 3、4、1，数 3 个空位落到位置 1，填 3；填 4 时从位置 1 往后数 4 个空位，空位是 3、4、0、2？位置 0 有 1、位置 2 有 2，空位只有 3、4，数 4 个会绕两圈，落到位置 4？这样推下去和样例对不上。
换一种更可靠的推导方式：直接模拟接收过程，反推排列。已知接收顺序是 1, 2, …, n，我们要确定每个编号在环上的位置。设pos[v]表示编号 v 在环上的位置。接收第 1 个是编号 1，位置任意，设pos[1] = 0。接收第 2 个是编号 2，它是在编号 1 之后间隔 1 颗未接收卫星后到达的。此时未接收的卫星有 n-1 颗，编号 2 在环上的位置 = 从pos[1]往后数 2 个"未来会被接收但还没被接收"的位置？这个思路仍然绕。
最稳妥的做法是正向模拟构造：用一个数组表示环，初始全为 0（空）。按 k = 1 到 n 的顺序，把编号 k 放到环上。放编号 1 时，位置 0。放编号 k（k ≥ 2）时，从上一个放置位置last出发，往后数 k 个空位（空位指数组值为 0 的位置），把 k 放在数到的那个空位上。数的时候只数空位，跳过已填的。
用 n=5 手动推：数组 [0,0,0,0,0]，last=0。
- k=1：放位置 0，数组 [1,0,0,0,0]，last=0。
- k=2：从 last=0 往后数 2 个空位。位置 1 空（第 1 个），位置 2 空（第 2 个），放位置 2。数组 [1,0,2,0,0]，last=2。
- k=3：从 last=2 往后数 3 个空位。位置 3 空（1），位置 4 空（2），位置 0 已填跳过，位置 1 空（3），放位置 1。数组 [1,3,2,0,0]，last=1。
- k=4：从 last=1 往后数 4 个空位。位置 2 已填跳过，位置 3 空（1），位置 4 空（2），位置 0 已填跳过，位置 1 已填跳过，位置 2 已填跳过，位置 3 已填跳过？这里绕圈时已填的都跳过，空位只有 3 和 4，数到第 4 个会重复数。正确做法是每绕一圈空位重新数，位置 3（1）、位置 4（2）、位置 3（3）、位置 4（4），放位置 4。数组 [1,3,2,0,4]，last=4。
- k=5：从 last=4 往后数 5 个空位。空位只剩位置 3，数 5 次都落在位置 3，放位置 3。数组 [1,3,2,5,4]。
结果 [1,3,2,5,4]，和样例输出完全一致。验证接收过程：从位置 0 的 1 开始，间隔 1 颗未接收的，未接收的是 3,2,5,4，间隔 1 颗（3）落到 2，接收 2；间隔 2 颗（5,4）落到 3，接收 3；间隔 3 颗（5,4,5）落到 4，接收 4；间隔 4 颗（5,5,5,5）落到 5，接收 5。顺序 1,2,3,4,5，正确。
3.2 代码实现与复杂度控制
n ≤ 10000，直接模拟上述过程，每次数空位最多绕环若干圈，最坏 O(n^2) = 10^8，在 1 秒时限下 C++ 能过，Python 可能紧张。更优的做法是用树状数组或链表维护空位，但小学组复赛通常不要求，O(n^2) 的模拟在 n=10000 时实际运行远小于理论最坏值，因为空位越来越少，后期绕圈虽多但总步数可控。下面给 Python 实现，用列表模拟，注意数空位时的循环写法。
n = int(input()) ring = [0] * n last = 0 ring[0] = 1 for k in range(2, n + 1): cnt = 0 pos = last while True: pos = (pos + 1) % n if ring[pos] == 0: # 只数空位 cnt += 1 if cnt == k: # 数到第 k 个空位 break ring[pos] = k last = pos print(' '.join(map(str, ring)))外层循环 n-1 次，内层while每次至少走一步，最坏绕多圈。pos = (pos + 1) % n实现环状移动，ring[pos] == 0判断空位，cnt == k表示数够了。注意 k=2 时数 2 个空位，k=3 时数 3 个空位，这个"数 k 个"的规律是从手动推导中验证出来的，不是猜的。
用 n=13 验证样例 2：输出应为1 8 2 5 10 3 12 11 9 4 7 6 13。如果代码跑出来不一样，检查cnt == k还是cnt == k-1，这是最容易错的地方。手动推 n=5 时 k=2 数 2 个空位得到位置 2，如果数 1 个空位会得到位置 1，最终排列就错了。
提示：这类"构造 + 模拟"题，先在纸上用小数据（n=5）手动推一遍，把每一步的数组状态写下来，再对照代码输出，比直接调试快得多。
变式练习：如果题目改成"给定 n，输出接收顺序为 1 到 n 的排列中字典序最小的那个"，就需要在构造时优先选小位置，难度上升一个档次，属于省选级别，复赛不会这么考。复赛的卫星题只要构造出任意一个合法排列即可，上面的方法已经足够。
4. 粉刷匠：倒序处理是唯一正解
这道题 100% 数据 n, m, k 都到 10^6，正着模拟每次刷一整行或一整列，最坏 10^6 × 10^6 = 10^12 次操作，必然超时。正确思路是倒着看：最后一次刷的颜色会覆盖之前所有同位置的操作，所以从后往前处理，每次刷的行或列中，只有还没被后续操作覆盖的格子才计入答案。
4.1 倒序 + 行列标记的 O(k) 算法
维护两个标记数组：row_done[i]表示第 i 行是否已经被后续操作整行覆盖过，col_done[j]表示第 j 列是否已被覆盖。从第 k 次操作倒序处理到第 1 次：
- 如果当前操作是刷第 y 行、颜色 z：这一行中还没被覆盖的格子数是
m - col_done_count（总列数减去已被后续列操作覆盖的列数）。如果 z=1（蓝色），答案加上这个数。然后把row_done[y]标记为已覆盖，row_done_count加 1。 - 如果当前操作是刷第 y 列、颜色 z：这一列中还没被覆盖的格子数是
n - row_done_count。如果 z=1，答案加上这个数。然后标记col_done[y]，col_done_count加 1。
关键点：已经被覆盖的行再被刷，不会产生任何新的有效格子，直接跳过。这样每个操作 O(1)，总复杂度 O(k)。
#include <cstdio> bool row_done[1000005], col_done[1000005]; int ops[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", &ops[i][0], &ops[i][1], &ops[i][2]); } long long ans = 0; int row_cnt = 0, col_cnt = 0; // 已覆盖的行数、列数 for (int i = k - 1; i >= 0; i--) { int x = ops[i][0], y = ops[i][1], z = ops[i][2]; if (x == 0) { // 刷行 if (row_done[y]) continue; // 该行已被后续操作覆盖 if (z == 1) ans += (long long)m - col_cnt; row_done[y] = true; row_cnt++; } else { // 刷列 if (col_done[y]) continue; if (z == 1) ans += (long long)n - row_cnt; col_done[y] = true; col_cnt++; } } printf("%lld\n", ans); return 0; }ops数组存下所有操作再倒序，是因为输入是正序给的，必须全部读完才能从后往前处理。row_cnt和col_cnt分别记录已被后续操作覆盖的行数和列数，计算当前行剩余格子时用m - col_cnt，因为这一行中每一列如果已经被后续列操作覆盖，那个格子就不归当前行管了。同理列用n - row_cnt。
用样例 1 验证：n=2, m=2, k=2，操作0 1 1（第 1 行刷蓝）、1 2 1（第 2 列刷蓝）。倒序：先处理1 2 1，刷第 2 列蓝色，col_done[2]=false，答案加n - row_cnt = 2 - 0 = 2，标记col_done[2]=true，col_cnt=1。再处理0 1 1，刷第 1 行蓝色，row_done[1]=false，答案加m - col_cnt = 2 - 1 = 1，总答案 3。正确。
样例 2：操作0 1 1、1 2 0。倒序先处理1 2 0，刷第 2 列红色，z=0 不加答案，标记col_done[2]=true，col_cnt=1。再处理0 1 1，刷第 1 行蓝色，答案加m - col_cnt = 2 - 1 = 1。总答案 1。正确。
注意：
ans用long long，因为 n 和 m 到 10^6，蓝色格子数最多 10^12，int 存不下。这是本题最大的失分点，很多选手样例过了但大数据全错，就是溢出。
4.2 为什么正着模拟一定超时
正着模拟每次刷一行要改 m 个格子，刷一列要改 n 个格子，k 次操作最坏 k × max(n, m) = 10^6 × 10^6 = 10^12 次赋值，1 秒内 CPU 大约能做 10^8 到 10^9 次简单操作，10^12 差了三个数量级，必然超时。倒序处理把"改格子"变成"数格子"，每个操作只做常数次判断和加法，10^6 次操作轻松跑完。
这个"倒序 + 标记"的套路在竞赛里很常见，凡是"后面的操作覆盖前面的操作"这类题，都可以往这个方向想。比如"多次染色求最终颜色""多次覆盖求最终可见部分"，倒序处理往往是正解。
变式练习：如果题目改成"求最后有多少格子是红色"，只需把z == 1改成z == 0累加即可。如果改成"求每个格子最后被刷的颜色"，倒序处理时给每个格子记录第一次遇到的刷色操作，需要更细的数据结构，难度更高。
5. 易错点：四道题里最容易丢分的五个地方
这一章把阅卷和讲评中最常看到的失分点集中列出来，每条按"错在哪、为什么错、怎么答对"写。这些错误不是粗心，而是对题意或语言特性的理解偏差，考前过一遍能少丢几十分。
5.1 文件目录建错，代码全对也是零分
错在哪：选手把源程序直接放在 D 盘根目录，或者目录名用了中文题目名、大小写不对，比如建了Friend而不是friend。为什么错：题目明确要求"目录名称与英文题目名称相同"，评测系统按固定路径找文件，路径不对直接判零，代码写得再好也读不到。怎么答对：开考后第一件事不是读题，是先把四个目录friend、people、star、paint建好，每个目录里放对应源文件，文件名也用英文题目名加正确后缀（.cpp、.c、.pas）。交卷前用资源管理器逐层点开确认，别信"我记得建了"。
5.2 统计人口用 cin 不加优化，大数据超时
错在哪：n 和 m 都到 50000，用cin >>逐个数读，在部分评测机上耗时超过 1 秒。为什么错：cin默认与 C 标准流同步，每次读入有额外开销，数据量大时比scanf慢数倍。怎么答对：题目末尾专门提示了用scanf、printf，照做即可。如果坚持用cin，在main开头加ios::sync_with_stdio(false); cin.tie(0);，但小学组比赛建议直接用scanf，少一个出错环节。
5.3 粉刷匠答案用 int，大数据溢出
错在哪：ans声明成int，n=m=10^6 时蓝色格子数可达 10^12，超出 int 范围（约 2.1 × 10^9），输出负数或错误值。为什么错：C++ 的 int 是 32 位，加法溢出后回绕，样例数据小看不出来，大数据全错。怎么答对：凡是涉及 n × m 量级的计数，一律用long long，输出用%lld。前缀和的pre数组同理，题目说答案不超 2^31-1，但中间过程可能超，用long long最稳。
5.4 卫星题数空位时把已填的也算进去
错在哪：构造排列时，数间隔没有跳过已填卫星的位置，导致后续编号放错位置，样例 2 对不上。为什么错：题目规则明确"接收过的卫星不再接收第二次信号，即此卫星不计算在间隔的卫星数量中"，数空位时只数ring[pos] == 0的位置。怎么答对：内层循环里先判断if ring[pos] == 0再cnt++，已填位置直接跳过。写完用 n=5 手动推一遍，和样例输出逐位对照。
5.5 好朋友题漏判价格为 0 或超预算
错在哪：只判断了房号不等于 x，没判断prices[i] == 0和prices[i] > m，把不可卖或买不起的房算进候选。为什么错：题目说"Pi=0 时表示该房不可卖"，且小 B 资金有限，两个条件都是硬约束。怎么答对：三个continue一个不能少，写完用样例 1 和样例 2 各跑一遍，再自己造一组"最近房不可卖、次近房超预算"的数据验证。
6. 考场时间分配与四题得分策略
150 分钟做四道题，平均每题 37 分钟，但四道题难度不是均分的。合理的分配是：前 10 分钟建目录、读全部题目、确认输入输出格式；好朋友 20 分钟，统计人口 25 分钟，卫星 40 分钟，粉刷匠 40 分钟，留 15 分钟检查文件和边界数据。前两题必须在前 55 分钟内写完并过样例，否则后面两题时间不够。
得分策略上，好朋友和统计人口目标是 200 分全拿，这两题没有思维难度，失分只可能来自实现细节，写完立刻用样例和自造数据验证。卫星题先写 O(n^2) 模拟，过 n=1000 的数据拿 50 分，如果时间充裕再想优化；粉刷匠先写正着模拟拿 30% 的 1000 规模数据，再改倒序拿满分。这种"先保底再冲高"的顺序比死磕一道题划算得多。
| 题目 | 目标分 | 建议用时 | 保底做法 | 冲高做法 |
|---|---|---|---|---|
| 好朋友 | 100 | 20 分钟 | 枚举 + 三重过滤 | 同左，无优化空间 |
| 统计人口 | 100 | 25 分钟 | 前缀和 + scanf | 同左 |
| 卫星 | 50~100 | 40 分钟 | O(n^2) 模拟构造 | 树状数组优化（可选） |
| 粉刷匠 | 30~100 | 40 分钟 | 正序模拟拿 30% | 倒序 + 行列标记 |
检查环节别省。交卷前做三件事：逐题确认目录名和文件名大小写；把四题的样例输入重新跑一遍，输出逐字符比对；检查所有计数变量是否用了long long。这三件事花 10 分钟，能拦住大部分非智力失分。
我带学生做模拟赛时见过太多次这种情况：代码逻辑全对，目录名写成Friend，四个测试点全零，孩子出来还挺高兴说都过了样例。从那以后我每次赛前都强制走一遍"建目录、写文件、跑样例、查溢出"的固定流程，不跳步。希望帮到你。
本文还有配套的精品资源，点击获取
