简介这份资源是第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 验证n6, x2, m600价格序列 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不对n6 应该有 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(nm)题目给 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这样x1时pre[x-1]就是pre[0]不需要特判。输出用%lld对应long long用%d会输出错误值这是 C 语言选手最常见的翻车点之一。题目末尾专门提示输入输出数据比较多建议用 scanf、printf这不是客套话。50000 行输入用cin在部分老评测机上会慢到超时用scanf是稳妥选择。如果坚持用cin至少加ios::sync_with_stdio(false)。用样例验证n4, m2人口 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]不需要对 x1 做特殊处理。变式练习如果询问改成编号 x 到 y 的人在家其余不在家求能核查到多少答案就变成pre[y] - pre[x-1]本身逻辑反过来而已。再难一点如果询问是编号 x 到 y 的人不在家但编号 z 的人临时回来了就需要在前缀和基础上做单点修正考的是对前缀和可减性的理解。3. 卫星约瑟夫环的逆向构造怎么推这道题是整卷的分水岭。50% 数据 n ≤ 1000100% 数据 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 步。用 n5 验证填 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。放编号 kk ≥ 2时从上一个放置位置last出发往后数 k 个空位空位指数组值为 0 的位置把 k 放在数到的那个空位上。数的时候只数空位跳过已填的。用 n5 手动推数组 [0,0,0,0,0]last0。k1放位置 0数组 [1,0,0,0,0]last0。k2从 last0 往后数 2 个空位。位置 1 空第 1 个位置 2 空第 2 个放位置 2。数组 [1,0,2,0,0]last2。k3从 last2 往后数 3 个空位。位置 3 空1位置 4 空2位置 0 已填跳过位置 1 空3放位置 1。数组 [1,3,2,0,0]last1。k4从 last1 往后数 4 个空位。位置 2 已填跳过位置 3 空1位置 4 空2位置 0 已填跳过位置 1 已填跳过位置 2 已填跳过位置 3 已填跳过这里绕圈时已填的都跳过空位只有 3 和 4数到第 4 个会重复数。正确做法是每绕一圈空位重新数位置 31、位置 42、位置 33、位置 44放位置 4。数组 [1,3,2,0,4]last4。k5从 last4 往后数 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) 的模拟在 n10000 时实际运行远小于理论最坏值因为空位越来越少后期绕圈虽多但总步数可控。下面给 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表示数够了。注意 k2 时数 2 个空位k3 时数 3 个空位这个数 k 个的规律是从手动推导中验证出来的不是猜的。用 n13 验证样例 2输出应为1 8 2 5 10 3 12 11 9 4 7 6 13。如果代码跑出来不一样检查cnt k还是cnt k-1这是最容易错的地方。手动推 n5 时 k2 数 2 个空位得到位置 2如果数 1 个空位会得到位置 1最终排列就错了。提示这类构造 模拟题先在纸上用小数据n5手动推一遍把每一步的数组状态写下来再对照代码输出比直接调试快得多。变式练习如果题目改成给定 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总列数减去已被后续列操作覆盖的列数。如果 z1蓝色答案加上这个数。然后把row_done[y]标记为已覆盖row_done_count加 1。如果当前操作是刷第 y 列、颜色 z这一列中还没被覆盖的格子数是n - row_done_count。如果 z1答案加上这个数。然后标记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 验证n2, m2, k2操作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]truecol_cnt1。再处理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 列红色z0 不加答案标记col_done[2]truecol_cnt1。再处理0 1 1刷第 1 行蓝色答案加m - col_cnt 2 - 1 1。总答案 1。正确。注意ans用long long因为 n 和 m 到 10^6蓝色格子数最多 10^12int 存不下。这是本题最大的失分点很多选手样例过了但大数据全错就是溢出。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声明成intnm10^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已填位置直接跳过。写完用 n5 手动推一遍和样例输出逐位对照。5.5 好朋友题漏判价格为 0 或超预算错在哪只判断了房号不等于 x没判断prices[i] 0和prices[i] m把不可卖或买不起的房算进候选。为什么错题目说Pi0 时表示该房不可卖且小 B 资金有限两个条件都是硬约束。怎么答对三个continue一个不能少写完用样例 1 和样例 2 各跑一遍再自己造一组最近房不可卖、次近房超预算的数据验证。6. 考场时间分配与四题得分策略150 分钟做四道题平均每题 37 分钟但四道题难度不是均分的。合理的分配是前 10 分钟建目录、读全部题目、确认输入输出格式好朋友 20 分钟统计人口 25 分钟卫星 40 分钟粉刷匠 40 分钟留 15 分钟检查文件和边界数据。前两题必须在前 55 分钟内写完并过样例否则后面两题时间不够。得分策略上好朋友和统计人口目标是 200 分全拿这两题没有思维难度失分只可能来自实现细节写完立刻用样例和自造数据验证。卫星题先写 O(n^2) 模拟过 n1000 的数据拿 50 分如果时间充裕再想优化粉刷匠先写正着模拟拿 30% 的 1000 规模数据再改倒序拿满分。这种先保底再冲高的顺序比死磕一道题划算得多。题目目标分建议用时保底做法冲高做法好朋友10020 分钟枚举 三重过滤同左无优化空间统计人口10025 分钟前缀和 scanf同左卫星50~10040 分钟O(n^2) 模拟构造树状数组优化可选粉刷匠30~10040 分钟正序模拟拿 30%倒序 行列标记检查环节别省。交卷前做三件事逐题确认目录名和文件名大小写把四题的样例输入重新跑一遍输出逐字符比对检查所有计数变量是否用了long long。这三件事花 10 分钟能拦住大部分非智力失分。我带学生做模拟赛时见过太多次这种情况代码逻辑全对目录名写成Friend四个测试点全零孩子出来还挺高兴说都过了样例。从那以后我每次赛前都强制走一遍建目录、写文件、跑样例、查溢出的固定流程不跳步。希望帮到你。本文还有配套的精品资源点击获取