少儿信息学复赛卷解析：枚举、前缀和、构造模拟与倒序扫描

简介第18届绍兴市少儿信息学竞赛复赛试题以单份 Word 文档形式呈现面向小学阶段参加信息学竞赛、准备 NOIP 入门训练的学生及辅导教师可用于熟悉复赛题型、检验编程基础与开展模拟测试。文档完整收录“好朋友”“统计人口”“卫星”“粉刷匠”四道题的题目一览、输入输出格式、样例解释和数据范围并附比赛目录结构示例与提交注意事项便于读者理解赛场文件组织方式。题目涉及数组与循环、条件判断、线性统计、环状模拟和行列刷色等知识点能帮助学习者从基础语法过渡到算法设计练习按规范读写文件与处理边界数据。压缩包共1个 docx 文件大小约32KB轻量易取用。目前已有815人学习或下载适合作为少儿信息学复赛真题训练与教师选题参考。1. 150 分钟四道题这套少儿组复赛卷的“手感”到底难在哪翻到卷子最后一页看到时间栏写着 150 分钟四道题每题 10 个测试点、每点 10 分第一反应是这题量对小学生不算轻。这是某市第十八届少儿信息学竞赛复赛的原卷文件名 IO、目录结构、根目录提交一整套流程和早年 NOIP 的赛制几乎一模一样考的是选手能不能在时间压力下把读题、建模、写代码、造数据自查跑完整。四道题正好卡在四个台阶上枚举、前缀和、构造模拟、倒序扫描恰好是信息学入门到提高之间最关键的那批套路拿它当限时自测题比零散刷题更能暴露问题。2. 「好朋友」与「统计人口」枚举与前缀和签到题也分快慢这两道题放在卷子前两位分值一样是 100 分处理方式却完全不同第一道是纯枚举n 只有 100怎么写都过第二道 n 和 m 都到 50000写歪一点就是满屏 TLE。很多选手栽在不该栽的地方——不是不会算法是 scanf 没写、数组没开够、边界差一。下面两节分别把这两道题的建模、代码和参数抠清楚。2.1 「好朋友」距离由近到远枚举第一个买得起的就收手题目场景很朴素一条直线上 n 套房相邻间距 10 米小 A 住 x 号小 B 要在剩下的房子里买一套离小 A 最近的预算 m 元价格为 0 表示这套房不可售求最近距离。这题的建模要点是把「最近」翻译成「按距离步长递增扫描」。距离 d 步对应房号 x−d 和 xd从 d1 开始往上加每次优先看右边、再看左边因为输出的是距离不是房号先看哪边不影响答案只要有一边满足「价格大于 0 且不超过预算」就立刻输出 d×10 并结束。这个「找到即停」的写法把复杂度压到 O(n)也顺手避开了「两家距离相同怎么选」这种容易纠结死的分支。#include cstdio const int MAXN 105; int p[MAXN]; int main(){ freopen(friend.in, r, stdin); freopen(friend.out, w, stdout); int n, x, m; scanf(%d %d %d, n, x, m); for(int i 1; i n; i) scanf(%d, p[i]); for(int d 1; d n; d){ // d 是房号差也就是走了几步 int r x d, l x - d; if(r n p[r] 0 p[r] m){ // 右边先看能买就直接定答案 printf(%d\n, d * 10); return 0; } if(l 1 p[l] 0 p[l] m){ // 右边不行再看左边 printf(%d\n, d * 10); return 0; } } return 0; // 理论上不会走到这里题面保证有解 }freopen两行是这套卷子的硬性要求输入文件名friend.in、输出文件名friend.out和题目英文名完全对应大小写也不能改。d n的上界取 n−1 足够因为两端最远就是 n−1 步。p[r] 0这个条件和p[r] m必须同时成立很多人只写了后者结果把不可售的房子当成 0 元买走了样例能过、隐藏点全挂。这道题的样例在 docx 里是粘连的看一眼就知道不对第一行本该是6 2 60第二行0 0 80 56 89 0粘在一起就成了题面里那串6 2 600 0 80 56 89 0。按输出 20 反推x2 时距离 1 的位置是 1 号和 3 号1 号价格 0 不可售、3 号 80 超出预算 60距离 2 的 4 号价格 56 在预算内答案正好 20 米。样例 2 同理6 3 50配上51 0 0 62 72 46才对得上输出 30。拿到这种卷子第一件事是拿样例解释反推真实输入别硬按粘在一起的数字调。另外一个坑在数据范围那一行原文写的是1≤m≤n还冒出来一个从未定义过的 k。m 是资金样例里都到 600 了显然不是房号范围k 是排版残留。以题面和样例为准别被这行字带偏去给 m 加莫名其妙的约束。2.2 「统计人口」把「不在家的人」换成一个减法第二题的描述绕了一层n 户人家线性排列给出每户人口 aᵢ然后 m 次询问每次给出 x、y表示编号 x 到 y 的住户不在家问这次能核查到多少人口。新手容易直接照着描述写每次询问把 x 到 y 标成不可用再从头到尾累加一遍。复杂度 O(nm)n 和 m 都是 50000 的时候是 2.5×10⁹ 次运算一秒的时限下必然超时这就是典型的时间复杂度翻车。正确的翻译是**「核查到的人口 总人口 − 区间 [x,y] 的人口」**。总人口一次算好区间和用前缀和 O(1) 拿到整个程序降到 O(nm)。前缀和这个结构在这里的价值不是「快一点」是把每次询问从跟 n 挂钩变成跟常数挂钩量级上直接掉一个维度。#include cstdio const int MAXN 50005; int a[MAXN]; long long pre[MAXN]; // 前缀和必须开 long long int main(){ freopen(people.in, r, stdin); freopen(people.out, w, stdout); 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]; // pre[i] a[1] ... a[i] } for(int i 1; i m; i){ int x, y; scanf(%d %d, x, y); // 不在家的是 [x,y]能核查的就是 sum(1..x-1) sum(y1..n) printf(%lld\n, pre[n] - (pre[y] - pre[x-1])); } return 0; }pre[0]必须是 0这是整个前缀和的下标基准pre[x-1]在 x1 时正好取到pre[0]所以不需要额外特判左端点。pre[n]是固定的总人口可以提前算出来存成变量省一次访存但对这道题的量级影响不大。这道题真正的敌人是输入输出。n 加 m 行、每行两个整数最坏接近 15 万个整数用cin 且没关同步的话在某些老评测机上能吃掉几百毫秒加上本身的计算量就贴着时限跑了。题面末尾专门写了「建议用 scanf、printf」这不是客套话是出题人提前告诉你测试点规模够大。我一般直接在文件开头写ios::sync_with_stdio(false); cin.tie(0);但既然题面点名 scanf就老老实实用 scanf少一个变量少一分风险。还有一个细节a[i]用 int 存没问题单户人口不会太大但pre一定要 long long。虽然题面写了「保证答案不超 2³¹−1」那是保证单个答案不代表中间过程安全前缀和累加过程中的溢出是血泪经验里最常见的一类隐性错误——样例全过大数据全错还查不出来。2.3 两道签到题的共同底线把这两题放在一起看能看出一套很稳定的出题逻辑第一题考「你会不会按题意老老实实枚举并处理边界」第二题考「你会不会把重复计算的东西提前算好」。前者考细心后者考建模。从工程角度看这两题还各有一个隐蔽的检查点值得记住。第一题的检查点是**「0 是特殊值不是价格」所有涉及 0 的判定都要单独想一遍第二题的检查点是「下标从 1 开始前缀和的 pre[0] 必须存在」**凡是差分、前缀和、区间查询下标 0 那个位置就是整个结构的锚点漏了它整条链都错位。写这两题的时间控制在 15 分钟以内比较合理剩下的时间要留给后面两道。如果在前两题上花了半小时还在调样例说明基本语法和输入输出格式还不够熟这套卷子暴露的就不是算法问题而是基本功问题。3. 「卫星」环形约瑟夫变种先模拟再构造第三题是整张卷子里最容易读错题意的一道。题目给了 n 颗卫星排成一个环要你设计一个排列顺序使得按规则接收信号时接收到的编号正好是 1、2、3……n。规则本身有点绕先收 1 号然后「间隔 1 颗」收到 2 号接着「间隔 2 颗」收到 3 号每次间隔的颗数等于上一次收到的卫星编号已经收过的卫星不再计入间隔。这个「已接收的不计入间隔」是整个题眼。如果理解成「跳过 k 个物理位置」样例 1 立刻就推不通理解成「跳过 k 个还没被接收的卫星」样例才对得上。第 3 步从 2 号出发间隔 2 颗跳过的是 5 号和 4 号绕回 1 号时它已经被收过所以不计落到 3 号——这段解释就是判题的分水岭。3.1 用样例把规则跑一遍确认「间隔」到底怎么数拿 n5、排布1 3 2 5 4手推一遍最直观。此时环上的相邻关系是 1→3→2→5→4→1。第一步收 1 号位置定死。第二步间隔 1 颗从 1 号往后走跳过 3 号落到 2 号。第三步间隔 2 颗从 2 号往后走5 号和 4 号各算一颗再往后是 1 号但已收过不计落点是 3 号。第四步间隔 3 颗从 3 号往后5、4 各一颗绕回 1、2、3 都已收过不计再数一个 5 号凑满三颗落点 4 号。第五步只剩 5 号间隔 4 颗怎么数都落在它身上。推完这五步就能提炼出可执行的判断从当前位置出发往后遇到已接收的位置直接跳过数满 k 个未接收的位置再停下来的那个未接收位置就是下一个接收点其中 k 等于上一次接收到的编号。这个描述可以一行一行翻译成代码不需要任何额外推导。3.2 反向构造按接收顺序往环上填编号正向模拟是「给定排布求接收顺序」题目要求的是反过来的「给定接收顺序求排布」。直接正向搜索会炸但反过来想会非常干净。把环看成 n 个空位按接收顺序第 i 次接收的是编号 i。当我们放置编号 i 时环上已经有 i−1 个位置被占住了这些位置对应的编号都小于 i也就是「已经被接收过」。而规则说的是「间隔的只有未接收的卫星」所以这 i−1 个已占位置在数数时必须被跳过。于是构造规则就变成了第 i 步从第 i−1 步落点的下一个位置开始往后走数到第 i 个空位把编号 i 填进去。为什么是第 i 个因为间隔数是 i−1上一次接收的就是 i−1 号跳过 i−1 个空位之后落脚的那个就是第 i 个空位。第一步把 1 号放在位置 1这是平移对称性决定的从哪个位置起手都可以输出任意一个合法排布即可。#include cstdio const int MAXN 10005; int ans[MAXN]; // ans[pos] 放在 pos 位置的卫星编号0 表示空位 int main(){ freopen(star.in, r, stdin); freopen(star.out, w, stdout); int n; scanf(%d, n); int pos 1; ans[1] 1; // 1 号卫星放在 1 号位置 for(int i 2; i n; i){ int cnt 0; while(cnt i){ // 从当前位置往后数第 i 个空位 pos pos % n 1; // 环形推进超过 n 回到 1 if(ans[pos] 0) cnt; } ans[pos] i; } for(int i 1; i n; i) printf(%d%c, ans[i], i n ? \n : ); return 0; }pos % n 1是环形下标的惯用写法比if(pos n) pos 1;少一个分支n 为 1 时也不会越过边界。while(cnt i)里的 i 就是「第 i 个空位」它和间隔数 i−1 是差一关系这两者混淆是这道题最常见的翻车点写成cnt i - 1会整体错位一位样例 2 那种长排布立刻崩。空位判断用ans[pos] 0就够了因为编号从 1 开始0 天然可以作为哨兵。如果题目编号从 0 开始就得换一个初始值这是很常见的边界改动。3.3 复杂度与上限n10⁴ 时 O(n²) 够用但要知道更稳的写法外层循环 n 次内层 while 平均推进距离和剩余空位数成正比总复杂度 O(n²)。题面给的 100% 数据是 n ≤ 10000最坏情况下内层累计大概 10⁸ 次自增和判断C 在 1 秒时限下勉强能过但不同评测机的常数差异很大我一般会按「能过但别指望宽裕」来评估。如果 n 往上加到 10⁵这个写法就不能要了。标准做法是用树状数组维护空位的前缀和query(pos)拿到当前位置之前有多少空位再二分或者用树状数组的倍增找第 k 个空位单次 O(log n)总体 O(n log n)。这种做法在这道题里不是必须的但值得记住因为「在环形序列中不断删除元素并找第 k 个存活位置」是一整个题族的共同结构约瑟夫问题、排队问题、卡牌问题都是它。对小学生组来说考场上把 O(n²) 写对、把样例 2 那组 13 颗卫星的输出跑通性价比远高于临时扣树状数组。这里的分寸感很关键先确认自己算清楚了复杂度上限再决定要不要优化不要一上来就上高级结构结果常数爆炸也不要明明超了还硬交。验证方法很简单程序输出后自己写一个正向模拟器按输出排布跑一遍接收过程把接收到的编号序列打出来看是不是 1 到 n。这个自检脚本比肉眼看输出可靠得多尤其是 n 稍大一点的时候。4. 「粉刷匠」正序模拟必炸倒序扫描才是解第四题是整张卷子里最像「工程题」的一道。n 行 m 列的网格k 次操作每次把一整行或者一整列刷成红或蓝问最后有多少个蓝色格子。数据规模是 n、m、k 全部到 10⁶这个量级直接封死了所有按格子模拟的路。很多人的第一反应是开一个 n×m 的二维数组每次操作把对应的行或列遍历一遍染色最后统计。nm10⁶ 时这个数组本身就要 10¹² 个元素连声明都过不了编译。这个思路必须彻底放弃不能抱侥幸心理去做「开一行刷一行」的折中。4.1 正序为什么不行后刷的会覆盖先刷的就算不考虑内存把每个格子都刷一遍的复杂度也是 O(k·max(n,m))最坏 10¹² 次写入一秒时限连一成都不够。更根本的问题在于覆盖。正序处理时你知道当前这次操作会把整行刷成某个颜色但不知道后面还有多少次操作会覆盖其中一部分。要算出最终蓝色格子数必须知道每个格子最后一次被刷是什么颜色。正序的信息链是断的你得存下每个格子的最新状态才能往下走而那正好是开不下的那个二维数组。倒过来看信息链就通了。4.2 倒序扫描 行列标记只处理「第一次见面」的行和列从最后一次操作往前扫每条操作只关心一件事这一行或这一列在后面有没有被处理过。如果已经被后面的操作覆盖过那这次操作对最终结果没有任何影响直接跳过如果没有那这一整行或这一列的最终颜色就由这次操作决定之后不会再变。这里「被处理过」需要一个标记数组。行标记数组大小 n1列标记数组大小 m1都是布尔型加起来也就 2MB 左右完全在内存里。真正的技巧在计数上。假设现在倒序扫到一次「把第 r 行刷成蓝色」的操作并且第 r 行之前没被处理过。那这一行上究竟有多少个格子最终是蓝色答案是这一行上所有还没被后续列操作覆盖过的格子数量正好等于「当前剩余的、未被处理的列数」。因为那些列在更晚的时刻会被整列刷掉颜色不由这一行决定剩下的列没有更晚的操作就保留这一行的蓝色。所以维护两个计数器leftRow表示还没被行操作覆盖的行数初始为 nleftCol表示还没被列操作覆盖的列数初始为 m。倒序遇到一次未处理过的行操作如果是蓝色就ans leftCol然后把leftRow减一列操作对称处理。#include cstdio const int MAXN 1000005; int opx[MAXN], opy[MAXN], opz[MAXN]; // 离线存下所有操作倒序要用 bool visRow[MAXN], visCol[MAXN]; int main(){ freopen(paint.in, r, stdin); freopen(paint.out, w, stdout); int n, m, k; scanf(%d %d %d, n, m, k); for(int i 1; i k; i) scanf(%d %d %d, opx[i], opy[i], opz[i]); long long ans 0; int leftRow n, leftCol m; for(int i k; i 1; i--){ // 从最后一次操作往前扫 if(opx[i] 0){ // x0 表示刷行y 是行号 int r opy[i]; if(visRow[r]) continue; // 这一行后面被刷过本次作废 visRow[r] true; if(opz[i] 1) ans leftCol; // 该行上尚未定色的格子全变蓝 leftRow--; // 这一行的最终颜色已确定 }else{ // x1 表示刷列 int c opy[i]; if(visCol[c]) continue; visCol[c] true; if(opz[i] 1) ans leftRow; leftCol--; } } printf(%lld\n, ans); return 0; }用样例 1 走一遍两次操作第一次刷第 1 行蓝色第二次刷第 2 列蓝色。倒序先看到第二次列 2 未访问ans leftRow此时是 2ans 2leftCol变成 1。再看到第一次行 1 未访问ans leftCol现在是 1ans 3leftRow变成 1。输出 3和样例一致。样例 2 把第二次操作换成刷红色倒序处理时列 2 虽然被处理了但z0不加贡献leftCol同样减一。然后行 1 蓝色加上剩下的leftCol1答案 1也对。ans必须用 long long。n 和 m 都是 10⁶最坏情况蓝色格子数接近 10¹²int 直接溢出。这是这道题最典型的隐性错误样例小、根本看不出来。4.3 一百万个操作读入和内存都得算清楚k 到 10⁶意味着要存三百万个整数。三个 int 数组各 10⁶ 元素一共 12MB加上两个 bool 数组各 1MB总共 14MB 左右。如果评测机内存限制是 64MB这个开销是安全的如果是 32MB就得考虑把opz压成 char或者在读入时把小操作合并——不过按这套卷子给小学组的资源水平14MB 不会成为瓶颈。真正容易出问题的是读入速度。三百万个整数用cin不开同步优化的话光读入就够喝一壶。题面末尾那句「建议用 scanf、printf」对这道题尤其要紧老老实实scanf是最省事的方案。另一个细节是freopen的文件名paint.in和paint.out和题目英文名对应。这道题的名字里没有数字也没有下划线看着简单反而更容易手滑打错一个字母本地跑得欢、交上去零分。5. 常见问题排查五个坑每一个都有人踩过5.1 题面与样例里的排版坑现象按题面给的样例输入粘进程序跑出来的结果和样例输出对不上怎么改代码都不对。第一题的样例输入里出现了 8 个数字但题目说第一行只有 3 个。原因docx 转文本时行内空格丢失第一行的第三个数字和第二行的第一个数字粘成了一个数。第一题实际是6 2 60加0 0 80 56 89 0第二题实际是6 3 50加51 0 0 62 72 46粘完就变成了600 0 80、5051 0 0这种读不通的形态。数据范围那一行里凭空出现的1≤k≤100也是排版残留题目里根本没有 k 这个变量。解决拿到任何一份文档版题目先用样例解释反推输入。第一题输出 20 对应房号 4、第二题输出 30 对应房号 6反推出来的预算分别是 60 和 50和看输出解释完全自洽。反推不出来的说明样例本身就是错的那就按题面描述写别被样例带跑。5.2 文件名与目录结构的坑现象本地样例全过提交后 0 分。原因这套卷子用的是文件名 IO不是标准输入输出。程序里必须有freopen(xxx.in, r, stdin)和freopen(xxx.out, w, stdout)而且文件名必须和题目英文名逐字符一致。另一个高频翻车点是目录名题目要求选手为每题建立与英文题目名同名的目录源程序放在对应目录下整个选手目录再放进根目录。目录名写成大写、写成中文、或者把四个源文件全堆在选手目录下都可能被判为无法识别。解决写完一题立刻建目录、放文件、用相对路径编译一次确认能读到xxx.in。四道题的目录名分别是friend、people、star、paint全小写和英文题目名一一对应。正式提交只交源程序不交可执行文件这一点题面写得很清楚。5.3 边界与特殊值处理的坑现象第一题样例通过提交后部分测试点 WA。原因漏掉了P[i] 0这个条件把不可售的房子当成 0 元可买于是答案偏小。第二题漏掉了x 1时的pre[0]或者把前缀和数组开成 int超大测试点溢出。解决凡是题目里出现「0 表示某种特殊含义」的描述都要在代码里单独写一条判定不能顺手用p[i] m一把梭。前缀和的pre[0] 0是结构的一部分不是可选项累加数组一律 long long宁可多占 4 字节不要事后查溢出。5.4 复杂度估算的坑现象第三题本地跑 n1000 秒出提交后 n10000 的点 TLE。原因O(n²) 的构造在 n10000 时是 10⁸ 量级本地机器快、编译器开优化可能刚好压在时限内评测机慢一点、常数大一点就直接超了。解决写之前先按最坏数据估一遍操作次数卡在 10⁷ 以内比较安全10⁸ 就得考虑优化。第三题如果不想赌直接上树状数组找第 k 个空位第四题如果内存吃紧把opz从 int 换成 char或者读入时做一次相邻操作的合并。5.5 读入速度的坑现象第二题和第四题逻辑完全正确但大数据点超时。原因用cin 读入十万级以上的整数并且没关同步。解决题面里给了提示的地方就照着做scanf/printf是这两道题最稳的选择。如果坚持用 cin至少加上ios::sync_with_stdio(false); cin.tie(0);但要注意加了之后就不能再混用 scanf否则读入顺序会乱。6. 拿这套卷子做限时自测目录结构、对拍与复盘这套卷子的价值不在题目本身有多难而在它是一份完整的、带赛制的、可复现的评测环境样本。想让它真正发挥作用得按比赛的方式跑一遍而不是随便找台电脑把四道题写完就算。先按题面要求把目录搭出来。选手目录用编号命名四道题各一个子目录源程序放在对应目录下这一整套放在根目录# 选手目录与四道题的题目目录名称必须和英文题目名完全一致 mkdir -p sx001/friend sx001/people sx001/star sx001/paint # 编译时用相对路径确保 freopen 能找到同目录下的输入文件 cd sx001/friend g -O2 -o friend friend.cpp编译参数里-O2建议加上一是模拟评测机的优化选项二是能提前暴露未初始化变量这类在优化后才显形的错误。编译完不要直接跑先把题面样例按上一章反推出来的正确输入写进friend.in用文件重定向验证./friend friend.in # 程序内部已经 freopen这行只是为了对照 cat friend.out # 看输出是否等于 20四道题全部跑通样例只是最低要求。真正拉开差距的是自测数据的构造第一题可以造一个「最近的几套房都超预算、只有最远的买得起」的用例专门打「找到即停」写错的情况第二题造 n50000、m50000 全区间询问的压力数据看时间第三题用 n10000 跑一次再用前面说的正向模拟器验证输出的正确性第四题造 k10⁶ 且行列交替刷的数据专门测倒序逻辑和 long long。对拍这一步我强烈建议做第三题。写一个二十行的正向模拟器读入你的输出排布和 n按规则跑一遍打印接收序列和 1 到 n 比对。这个脚本比盯着输出看快十倍而且能覆盖到 n13 这种样例之外的情况。第四题的对拍稍微麻烦些可以写一个 n、m、k 都很小的暴力版本随机生成几千组数据两边对跑暴力的那个开二维数组逐格刷就行。复盘的时候别只看哪题没过要记录三件事哪一步卡住了读题、建模、调样例、还是优化、卡了多久、下次遇到同类结构能不能直接反应出解法。我自己带人做这套卷子的经验是卡住的位置往往高度集中——第一题卡在特殊值、第二题卡在复杂度、第三题卡在读题、第四题卡在正序思维。把这四个卡点记下来比刷十套新题都有用。从那以后我每次拿到这种文档版题目第一件事都是把样例输入按输出解释反推一遍、把目录结构和文件名对照检查一遍确认这两件事之后再动手写代码。这个习惯救过我很多次尤其是在那些题面和样例看起来都不太对劲的卷子上。希望帮到你。本文还有配套的精品资源点击获取