简介这份资源是第18届绍兴市少儿信息学竞赛复赛试题文档面向备战NOIP等编程竞赛的小学高年级及初中选手也适合信息学教练用作课堂练习与模拟测试素材。压缩包内共1个docx文件约32KB完整收录了比赛题目一览、目录结构示例与特别提醒并包含“好朋友”“统计人口”“卫星”“粉刷匠”四道题的题面、输入输出格式、样例及数据范围说明覆盖数组与循环、前缀和与区间查询、环形模拟、网格染色等算法与数据结构知识点。资源已有815人学习下载读者可据此还原150分钟复赛环境按题目目录规范练习源程序提交对照样例与数据范围检验算法效率是了解绍兴市少儿信息学竞赛命题风格、进行针对性训练的一份实用赛题材料。1. 一份小学竞赛卷子为什么值得成年人翻一翻朋友发来一个文件名字很长叫“第18届绍兴市少儿信息学竞赛复赛试题”。他问我小学的题是不是就加减乘除加点逻辑我打开看了一眼四道题两个半小时最后一题的规模到了百万级。这就有意思了——它表面上是给孩子的卷子骨子里却把信息学竞赛最核心的几类思维摆得明明白白怎么在限制里找最优、怎么把重复计算省掉、怎么在环上推位置、怎么倒着看问题。很多人听到“信息学”三个字第一反应是敲代码。其实这套题真正考的不是打字速度而是把一段生活化的描述翻译成可计算模型的能力。房子排成一条线、人口按户编号、卫星围成一圈、墙面刷来刷去全是日常场景但每一道背后都藏着一个经典套路。搞懂这四个套路你对“编程到底在编什么”这件事会有一个完全不同的认识。这份资料就是一份完整的复赛原题四道题的题面、样例、数据范围都在里面适合拿来当一面镜子照一照自己的思路卡在哪一层。2. 好朋友在一条直线上找“最近且买得起”2.1 题目到底在问什么把场景剥掉剩下的模型很干净一条数轴上有 n 个点编号 1 到 n相邻点间距固定 10 米。已知其中一个点 x 是“禁区”不能选。每个点有一个价格价格为 0 表示不可售。手里有 m 元问在买得起的前提下能选到的点里离 x 最近的距离是多少。注意这里的优先级先保证“买得起”再在买得起的里面找“离得最近”。不是先找最近的再看买不买得起。这个顺序一旦搞反样例就会打脸。样例 1 里 x2价格序列是 0、80、56、89、0预算 600。离 2 号最近的是 1 号和 3 号但 1 号价格是 0不可售3 号要 56 元买得起距离 10 米等等样例输出是 20。这里就得回头看1 号价格为 0 不可售3 号价格 56 买得起距离应该是 10 米才对。但样例解释写的是“可买的房号为 4 号”距离 20 米。这说明题面里的价格序列和房号的对应关系需要仔细对齐——价格是按房号顺序给的第一个数对应 1 号房。样例 1 的价格是 0、80、56、89、0对应 1 到 5 号房。3 号房价格 56预算 600明明买得起。样例却选了 4 号。这里最合理的理解是题面样例数据在转录时存在错位实际应以“买得起且最近”这个规则为准去推。这也提醒一件事拿到题先拿样例验自己的理解样例对不上多半是某个条件的读法偏了。2.2 为什么这题是“入门但不简单”数据范围 n 不超过 100意味着哪怕你把每个房子都扫一遍、对每个候选算一次距离、再比一次价格计算量也完全撑得住。所以这题不考算法复杂度考的是“边界条件想全了没有”。容易翻车的点有这么几个。第一x 自己不能选扫描时要跳过。第二价格为 0 的房子不可售不能因为“距离为 0 最诱人”就误选。第三距离是房号差乘 10不是房号差本身。第四如果所有可售房都买不起怎么办题面没有明说输出什么这种时候要看数据是否保证有解——从“保证操作合法”这类措辞看出题人通常默认有解但写代码时留一个兜底分支是血泪经验。用一段伪代码把思路固定下来n, x, m map(int, input().split()) price list(map(int, input().split())) best float(inf) for i in range(1, n 1): if i x: # 跳过小A自己家 continue if price[i - 1] 0: # 不可售 continue if price[i - 1] m: # 买不起 continue dist abs(i - x) * 10 if dist best: best dist print(best)这段代码里price[i-1]的下标偏移是最容易写错的地方因为房号从 1 开始而列表从 0 开始。best初始化为无穷大保证第一个合法候选一定能顶上来。整个循环只扫一遍逻辑直白适合刚接触竞赛题的人建立“读条件、写判断、更新答案”的基本节奏。2.3 它和“最短路”不是一回事有人看到“最近”两个字就往图论上想觉得要在房子之间连边跑最短路。这题根本没有图房子就是一条线距离是算出来的不是搜出来的。把简单模型复杂化是初学阶段很常见的自我消耗。判断标准很简单如果所有候选之间的关系能用一维坐标直接表达就不需要建图。3. 统计人口为什么“前缀和”是这类题的后悔药3.1 从“每次重新数”到“提前记好账”题面说得很清楚n 户人家排成一行每户有人口数。接下来 m 次询问每次给一个区间 [x, y]表示这个区间里的人都不在家问还能核查到多少人口。翻译一下总人口减去区间人口就是答案。最直觉的做法是每次询问都把区间内的数加一遍。n 和 m 都到 50000 的时候最坏情况是 50000 乘 50000二十五亿次加法一秒时限里绝对跑不完。这就是为什么题面专门提示“输入输出数据比较多建议用 scanf、printf”——出题人知道很多人会在这里翻车。省时间的办法是提前把账记好。定义一个数组 ss[i] 表示前 i 户的总人口。那么区间 [x, y] 的人口就是 s[y] - s[x-1]。一次减法代替一长串加法查询从“跟区间长度成正比”变成“常数时间”。这个技巧就是前缀和信息学里最朴素也最常用的预处理手段之一。n, m map(int, input().split()) a list(map(int, input().split())) s [0] * (n 1) for i in range(1, n 1): s[i] s[i - 1] a[i - 1] # 前i户的累计人口 total s[n] for _ in range(m): x, y map(int, input().split()) print(total - (s[y] - s[x - 1]))s的长度开到 n1是为了让s[0]0这个哨兵存在这样x1时s[x-1]不会越界。这个细节看着小但它是前缀和写法能不能一把过的关键。total单独存一份避免每次查询都去取s[n]读起来也更清楚。3.2 前缀和的本质是“用空间换重复劳动”打个比方你每天出门前都想知道这个月花了多少钱。笨办法是把每张账单翻出来加一遍前缀和的做法是每天睡前在日历上写一个“截至今天的累计数”以后想知道某几天的花销两个累计数一减就行。多记了一列数省掉了无数次重复加法。这也解释了它的适用边界数据是静态的、会被反复区间查询前缀和就非常合适。如果数据中途会被修改前缀和就不好使了因为改一个数后面所有累计值都得跟着改。那时候要换别的结构。这题的数据在查询前就固定了所以前缀和是正解。3.3 常见误区把“不在家”理解反了这题最容易搞混的地方不是算法是语义。题目问的是“能核查到多少人口”而给的是“不在家”的区间。有人一上来就把区间内的人口当成答案输出样例 1 第一问区间是 1 到 3人口 3159但正确答案是 6也就是第 4 户的 6 人。差的就是“总人口减去区间人口”这一步。读题时把“求什么”和“给什么”用两行字分别写下来能挡掉一大半这类错误。4. 卫星环形结构里“隔几个”到底怎么数4.1 规则拆解间隔数在变而且跳过已接收的这题是四道里描述最绕的。n 颗卫星排成一个环要设计一个排列使得按特定规则接收时收到的编号顺序恰好是 1 到 n。规则是先收 1 号然后间隔 1 颗收到 2 号再间隔 2 颗收到 3 号每次间隔的数量等于上一次收到的卫星编号。已经收过的卫星不再计数。拿 n5、排列 1 3 2 5 4 走一遍收 1间隔 1 颗跳过 3到 2间隔 2 颗从 2 往后数5 和 4 算两颗到 1但 1 已收过不计继续数到 3间隔 3 颗从 3 往后5、4、5 算三颗到 4间隔 4 颗一路数到 5。顺序正好 1 2 3 4 5。关键理解在于“间隔”数的是还没被接收的卫星已接收的直接跳过、不占名额。这跟约瑟夫环的计数方式很像但又不完全一样因为间隔步长是动态变化的不是固定值。4.2 正着模拟很难倒着想就通了如果按“给定排列、模拟接收”的思路去构造会陷入一个循环你不知道排列长什么样却要用排列去推接收顺序。换个方向既然最终接收顺序是 1 到 n那就可以从“接收顺序”反推“排列中每个位置放谁”。具体做法是维护一个“尚未被占用的位置”集合按接收顺序 1 到 n 依次放置。放第 k 个接收的卫星时需要从当前位置往后数 k 个空位因为间隔数等于上一次收到的编号而接收顺序是 1、2、3……所以第 k 步的间隔就是 k-1这里要小心题面说“每次间隔的卫星数量为上一次接收到的卫星编号”第一次收 1 之后间隔 1第二次收 2 之后间隔 2所以第 k 次接收后间隔 k。用有序结构维护空位、按排名取第几个空位就能在 O(n log n) 内构造出答案。import bisect n int(input()) slots list(range(1, n 1)) # 尚未占用的位置 ans [0] * (n 1) pos 0 # 当前在 slots 中的下标 for k in range(1, n 1): # 从当前位置起数 k 个空位k1 时就是当前空位 idx (pos k - 1) % len(slots) place slots.pop(idx) ans[place] k pos idx # 下一个起点是刚占位置的后一个空位 print( .join(map(str, ans[1:])))这段代码的核心是slots.pop(idx)把选中的空位从候选里删掉天然实现了“已占位置不再计数”。pos更新为idx因为删除后原来 idx 位置的元素被后一个顶上来了正好是“下一个空位”的起点。取模是为了让环闭合。n 到 10000 时列表删除是 O(n)整体 O(n²)在数据范围内可以接受如果规模再大就要换成树状数组按排名查空位。4.3 易混点环上的“间隔”和数组下标不是一回事初学者常犯的错是把“间隔 k 颗”直接写成下标加 k。在环上下标要取模而且被占的位置要跳过这两层处理叠在一起直接加会错得莫名其妙。稳妥的做法是先把“空位序列”单独维护出来在空位序列上做取模和删除物理位置和逻辑位置就分开了。这个分离思想在环形模拟题里非常通用。5. 粉刷匠百万级操作为什么必须倒着看5.1 正着刷的问题后面的会盖掉前面的n 行 m 列的墙k 次操作每次整行或整列刷成红或蓝问最后有多少蓝格子。正着模拟的话每次操作要改一整行或一整列k 到一百万、行列也到一百万乘起来是天文数字一秒时限里想都别想。问题的本质是一个格子最终是什么颜色只由“最后一次刷到它的操作”决定。前面的操作不管刷了多少次只要后面有一次覆盖就全白费。这个“只看最后一次”的性质是倒序处理的信号。5.2 倒序扫描每个格子只被算一次从最后一次操作往前看。遇到一次刷行操作如果这一行之前也就是更靠后的操作里没有被刷过那么这一行当前还“有效”的格子会被这次操作定色这些格子的数量等于“还没被刷过的列数”。定完色后这一行标记为已处理以后再遇到刷这一行的操作直接跳过。列同理。n, m, k map(int, input().split()) ops [tuple(map(int, input().split())) for _ in range(k)] row_done [False] * (n 1) col_done [False] * (m 1) free_cols, free_rows m, n # 尚未被任何行/列操作覆盖的列数、行数 blue 0 for x, y, z in reversed(ops): if x 0: # 刷第 y 行 if row_done[y]: continue row_done[y] True if z 1: blue free_cols # 这一行里还没被列操作定色的格子 free_rows - 1 else: # 刷第 y 列 if col_done[y]: continue col_done[y] True if z 1: blue free_rows free_cols - 1 print(blue)free_cols和free_rows是这段代码的灵魂它们记录“还有多少列/行没有被更靠后的操作碰过”。刷一行蓝色时能染蓝的格子数就是当前还没被列操作覆盖的列数。每处理一行free_rows减一因为这一行从此不再对后续更早的列操作贡献可染色格子。两个计数器一升一降每个操作只做常数次判断总复杂度 O(k)百万级也轻松。5.3 什么时候别倒着做倒序处理成立的前提是“覆盖具有最终性”也就是后写的完全决定结果。如果操作是“叠加”而不是“覆盖”比如每次刷是给格子加一层颜色、最后问平均色深那倒序就不适用了得换差分或其他手段。判断方法问自己一句“最后一次操作之后之前的所有操作还有没有影响”答案是没有才考虑倒序。6. 什么时候该用这套题什么时候别硬啃这套卷子最适合两类场景。一类是想摸清信息学竞赛入门到中档之间到底考什么的人四道题分别对应枚举加条件判断、前缀和、环形模拟加构造、倒序处理覆盖面很典型拿来做自测能快速定位自己卡在哪一类思维上。另一类是带初学者的人题面全是生活场景讲起来不枯燥样例也给得足适合拿来当“读题训练”的素材——先不写代码只把每题的输入、输出、约束用自己的话复述一遍对不上再回头看原文。不适合的场景也得说清楚。如果你已经在准备更高阶段的竞赛这四道题的算法难度偏低除了第四题的倒序思想还有点嚼头其余三题更多是基本功检验花两个半小时完整做一遍的性价比不高挑第四题和第三题做做即可。另外这份资料是试题文档不含官方题解和测试数据想靠它“刷题提分”是不现实的它的价值在于题面本身的质量和思维的代表性。我自己的习惯是每拿到一份这样的卷子先不看数据范围凭直觉写一版最笨的解法然后再回头看范围问自己“笨办法会在哪个数量级崩掉”。好朋友那题我第一版忘了跳过价格为 0 的房子样例一跑就露馅统计人口那题我一开始真就每次重新加看到 50000 才反应过来要前缀和。从那以后我每次读题都强制走一遍“先写约束、再想复杂度、最后对样例”的流程翻车次数明显少了。这份试题文档里四道题的完整题面和样例都在拿去按这个流程过一遍比只看别人讲思路扎实得多。希望帮到你。本文还有配套的精品资源点击获取