简介这份资源是第18届绍兴市少儿信息学竞赛复赛真题面向小学阶段的信息学竞赛选手与编程初学者。试卷共包含“好朋友”“统计人口”“卫星”“粉刷匠”四道题目分别涉及数组与循环处理、区间求和查询、环状序列构造以及行列染色模拟等典型场景覆盖变量与数据类型、控制结构、基础数据结构、算法设计等核心知识点能较全面地检验参赛者的编程基本功与问题建模能力。资源为单个docx文档体积仅32KB文件内保留了完整题面、输入输出格式、样例解释、数据范围约束及考场目录结构说明便于考生离线阅读、打印练习或模拟训练。目前已有811人下载学习适合用于备赛刷题、赛前模拟、校内信息学社团练习也可作为教师命题与教学参考。1. 一份少儿信息学竞赛复赛试题为什么值得反复刷《第18届绍兴市少儿信息学竞赛复赛试题》这份docx格式的卷子我拿到手先扫了一遍四道题第一反应是“这真的是小学组吗”好朋友、统计人口、卫星、粉刷匠四个题目名字很萌但卫星那题的约瑟夫环逆向构造、粉刷匠那题的行列时间戳优化放到NOIP普及组也能当训练题。它最适合两类人一是带信息学竞赛的教练拿来做阶段测验二是刚入门、想从真题里找编程手感的小学生和初中生。这套题没有偏题怪题每一道都在考“把题意转化成代码”的基本功刷完能摸清自己的薄弱点。2. 把四道题拆开看考点、数据范围与算法选型拿到一套真题先不要急着敲键盘。我习惯先把每道题的约束条件和预期复杂度写在草稿纸上避免后面被数据范围坑到。这套卷子的四个题数据范围从100到1000000不等正好覆盖了线性扫描、前缀和、约瑟夫环构造、时间戳优化这四类最核心的基础思维。2.1 好朋友线性扫描就是最优解先读题。小A住幸福村n套房排成直线房号1到n相邻距离10米。小A房号x。小B想买离小A最近的一套给出每套价格Pi0表示不卖和资金m。问最近距离。这个题的考点其实不是算法而是“能不能把生活场景翻译成循环里的条件”。数据范围n≤100意味着你用什么算法都能过线性扫描就够了。真正容易翻车的是三个条件房号i不能等于xPi必须大于0Pi必须小于等于m。三个条件必须同时满足。为什么线性扫描是最优解因为距离只取决于房号差的绝对值而数组是无序的不存在单调性可以利用。有人会想从x向两边扩展用双指针找第一个满足价格的房号但那样代码更绕而且还要处理越界。n只有100直接for i1..n维护最小值最稳。这类“数据范围小到不需要优化”的题目考的就是细心。这里有个小陷阱输出的是距离单位是10米。也就是输出|i-x|*10。很多人算出房号差就交忘记乘10样例恰好把差值2乘1020一眼能看出来但换一组数据就可能翻车。另外题目说“按房号顺序给定每套房的价格”所以输入顺序就是房号顺序不需要再排序直接按下标读入即可。2.2 统计人口前缀和把查询压到 O(1)这道题的数据范围一下子从100跳到50000。n户人家每户人口aim次查询每次给出[x,y]表示这些户不在家问能核查到多少人。朴素做法每次查询累加除了[x,y]之外的所有ai复杂度O(n*m)m,n最大50000直接超时。标准做法是前缀和。先预处理pre[i]pre[i-1]ai那么任意区间[x,y]的人口总和就是pre[y]-pre[x-1]。总人口total已知答案就是total - (pre[y]-pre[x-1])。这样每次查询O(1)。这里有一个很重要的竞赛习惯看到区间求和第一反应就是前缀和。不要因为“数据范围可能不大”就偷懒。另外题目提示“输入输出数据比较多建议用scanf、printf”这不是随便写的——用cin/cout在默认不关同步的情况下50000组输入输出可能卡掉不少时间虽然不算致命但竞赛里时间就是分数。还要注意答案范围题目保证所有答案不超2^31-1也就是说int够用。但前缀和数组建议用long long因为total和pre在累加时中间过程可能触及边界用long long更安心。printf时用%lld。这算是一种“赔率思维”多写一点避免溢出。2.3 卫星环状约瑟夫变体的逆向构造这是全卷最“烧脑”的一题。背景是n颗卫星排成环按规则接收先收1号然后间隔1颗收2号再间隔2颗收3号依此类推每次间隔数等于上一次收到的卫星编号。要求给出一个环状排列使得按这个规则能按1到n的顺序收到信号。很多选手第一次读题就卡在“间隔”的定义上。关键点接收过的卫星不参与计数但未接收的卫星在环上可以重复被数。比如n5时最后要间隔4颗但只剩一颗未接收于是4颗都是它。这是约瑟夫环的变体但比普通约瑟夫环多了一个“递增步长”。怎么构造排列一个很自然的逆向思路是先固定1号卫星在位置0然后按编号2到n依次决定每个编号放在环的哪个空位上。放2号时从1号位置出发跳过1个空位置放到下一个空位置放3号时从2号位置出发跳过2个空位置放到下一个空位置放i号时从i-1号位置出发跳过i-1个空位置。这里“空位置”就是还没放卫星的位置。用一个bool数组标记已占用每次模拟跳圈复杂度O(n^2)n≤10000完全扛得住。我用n5验证了一遍固定pos[1]0放2时跳过位置1放到位置2放3时从位置2数两个空位置3和4放到位置1放4时从位置1数三个空位置因为已占用的跳过最后放到位置4放5时只剩位置3无论怎么数都是它。得到的排列是1 3 2 5 4和样例一模一样。这个逆向构造是正解的核心。2.4 粉刷匠行列时间戳与排序计数最后一题看着像模拟实际是个计数优化题。n行m列墙k次操作每次把某整行或某整列刷成红色或蓝色后刷的覆盖先刷的。问最后蓝色格子数。n,m,k都可达1000000二维数组开不了直接模拟每次涂色也不行。突破口在于每个格子的颜色只取决于最后一次影响它的操作。我们可以记录每行最后一次被刷的时间rt[i]和颜色rc[i]每列最后一次被刷的时间ct[j]和颜色cc[j]。对于格子(i,j)如果rt[i] ct[j]说明行操作比列操作晚颜色由行决定否则由列决定。于是答案可以拆成两部分所有行最终是蓝色且行时间大于对应列时间的格子加上所有列最终是蓝色且列时间不小于行时间的格子。要高效统计把行时间和列时间分别排序然后用二分查找数个数。对每个蓝色行i它覆盖的蓝色格子数等于所有满足ct[j] rt[i]的列数对每个蓝色列j它覆盖的蓝色格子数等于所有满足rt[i] ct[j]的行数。两部分互斥直接相加。复杂度O((nm)log(nm))完美应对1e6的数据。这个技巧在竞赛里非常常用把二维问题拆成两个一维问题用时间戳解决覆盖顺序。类似的题目还有“矩形涂色最后颜色”等等掌握之后可以直接迁移。3. 动手复现C 参考实现与文件读写规范先明确比赛要求。原题在题目一览中给出了每个题对应的输入文件名和输出文件名比如好朋友是friend.in和friend.out而不是从屏幕读入。这意味着必须使用文件重定向。很多新手第一次参加机试不知道要加freopen结果程序一运行就报“找不到文件”。下面从目录结构开始讲。3.1 比赛目录结构源文件放哪里先搞清楚原题要求选手为每题建立与英文题目名相同的目录把源程序放到对应目录下最后把整个文件夹以考号命名放在D盘根目录。假设考号是sx001四题的英文名分别是friend、people、star、paint那么最终提交的目录结构应该是sx001/ ├── friend/ │ └── friend.cpp ├── people/ │ └── people.cpp ├── star/ │ └── star.cpp └── paint/ └── paint.cpp注意只交源程序不交编译后的exe。评测时系统会重新编译所以代码里的main函数必须返回0文件名不能带空格不要用IDE默认生成的“未命名1.cpp”。另外freopen里的文件名是相对路径评测时源文件就在对应题目目录下所以直接写friend.in就行不要加盘符路径。3.2 好朋友与统计人口的代码好朋友的参考实现如下#include cstdio #include cstdlib using namespace std; int main() { freopen(friend.in, r, stdin); freopen(friend.out, w, stdout); int n, x, m; scanf(%d%d%d, n, x, m); int bestDist -1; for (int i 1; i n; i) { int p; scanf(%d, p); if (i x) continue; // 不能买小A自己的房子 if (p 0 || p m) continue; // 不可卖或超出资金 int dist abs(i - x) * 10; // 相邻房子距离10米 if (bestDist -1 || dist bestDist) { bestDist dist; } } printf(%d\n, bestDist); // 题目保证有解无解时这里输出-1 return 0; }逻辑说明依次读入每套房价格排除条件后计算距离。用bestDist保存最小值初始-1表示尚未找到可买房子。n最大100扫描一遍足够。参数说明x是房号注意abs(i-x)10中的10别丢m是资金判断条件是pm而不是pm因为等于刚好买得起。如果题目保证有解可以忽略无解情况为了对拍方便保留-1输出。统计人口的参考实现#include cstdio using namespace std; const int MAXN 50005; long long pre[MAXN]; int main() { freopen(people.in, r, stdin); freopen(people.out, w, stdout); int n, m; scanf(%d%d, n, m); long long total 0; for (int i 1; i n; i) { int a; scanf(%d, a); total a; pre[i] pre[i - 1] a; } while (m--) { int x, y; scanf(%d%d, x, y); long long absent pre[y] - pre[x - 1]; printf(%lld\n, total - absent); } return 0; }逻辑说明pre[i]存前i户人口总和。查询时用pre[y]-pre[x-1]得到不在家人口总人口减去就是可核查人口。数据范围n,m50000O(nm)稳过。参数说明pre数组用long long因为虽然答案不超2^31-1但中间差值可能接近上限。printf用%lld对应long long。把pre定义成全局数组避免栈空间不足。3.3 卫星与粉刷匠的代码卫星的逆向构造参考实现#include cstdio #include vector using namespace std; int main() { freopen(star.in, r, stdin); freopen(star.out, w, stdout); int n; scanf(%d, n); vectorint pos(n 1, 0); // pos[i]表示编号i的卫星放在哪个位置 vectorbool used(n, false); // used[p]标记位置p是否已放卫星 used[0] true; pos[1] 0; // 先把1号放在位置0 for (int i 2; i n; i) { int skip i - 1; // 这次要间隔的卫星数 int cur pos[i - 1]; // 从上一次接收的卫星出发 int cnt 0; while (true) { cur (cur 1) % n; if (!used[cur]) { cnt; if (cnt skip) { // 已经跳过了skip个空位置下一个空位置放i cur (cur 1) % n; while (used[cur]) cur (cur 1) % n; break; } } } pos[i] cur; used[cur] true; } // 按位置输出卫星编号 vectorint ans(n, 0); for (int i 1; i n; i) ans[pos[i]] i; for (int i 0; i n; i) { if (i) printf( ); printf(%d, ans[i]); } printf(\n); return 0; }逻辑说明位置0固定给1号。每放编号i时从上一次接收位置pos[i-1]出发沿环数过skip个空位置把i放在下一个空位置。“空位置”就是还没放卫星的位置已占用位置跳过。当只剩一个空位置时绕圈后仍会回到它正好实现“重复计数”。n≤10000O(n^2)可以过。参数说明pos数组下标是卫星编号值是环上的位置索引used数组下标是位置索引。输出时反过来用ans数组把位置映射回编号。如果n1for循环不执行ans[0]1输出1。粉刷匠的时间戳统计参考实现#include cstdio #include vector #include algorithm using namespace std; int main() { freopen(paint.in, r, stdin); freopen(paint.out, w, stdout); int n, m, k; scanf(%d%d%d, n, m, k); vectorint rt(n 1, 0), ct(m 1, 0); vectorint rc(n 1, 0), cc(m 1, 0); for (int t 1; t k; t) { int x, y, z; scanf(%d%d%d, x, y, z); if (x 0) { // 刷第y行 rt[y] t; rc[y] z; } else { // 刷第y列 ct[y] t; cc[y] z; } } vectorint rowTime(rt.begin() 1, rt.end()); vectorint colTime(ct.begin() 1, ct.end()); sort(rowTime.begin(), rowTime.end()); sort(colTime.begin(), colTime.end()); long long ans 0; // 行比列晚颜色由行决定 for (int i 1; i n; i) { if (rc[i] 1) { int cnt lower_bound(colTime.begin(), colTime.end(), rt[i]) - colTime.begin(); ans cnt; } } // 列比行晚或行从未操作颜色由列决定 for (int j 1; j m; j) { if (cc[j] 1) { int cnt upper_bound(rowTime.begin(), rowTime.end(), ct[j]) - rowTime.begin(); ans cnt; } } printf(%lld\n, ans); return 0; }逻辑说明对每行每列记录最后刷的时间戳和颜色。行决策覆盖的列列时间 行时间列决策覆盖的行行时间 列时间。排序后二分统计数量。1e6的数据量下排序和二分都很快。参数说明rc/cc中0表示红色1表示蓝色对应题目里的z值。rt[i]0表示行从未被操作此时rc[i]为0不会进入蓝色统计。lower_bound返回第一个rt[i]的位置索引所以小于rt[i]的数量就是索引值。upper_bound返回第一个ct[j]的位置索引所以ct[j]的数量就是索引值。4. 避坑指南竞赛提交中的五个常见问题下面这些坑都是实际比赛中真实出现过的每条按“现象→原因→解决”写建议你对照自己的习惯检查。4.1 文件名和目录名对不上白交现象代码在本地跑得好好的交上去成绩是0分。 原因源文件命名成friend.cpp但目录名字打成了freind或者整个文件夹没有以考号命名。 解决赛前先看清楚英文题目名建目录时直接复制题目给的英文名不要手敲。提交前检查一遍文件路径确保是“D盘根目录/考号/题目英文名/题目英文名.cpp”。4.2 忘了加文件重定向现象自己测试时用键盘输入输出到屏幕一切正常评测时找不到输入文件直接运行时错误。 原因题目一览里明确写了输入文件名friend.in、输出文件名friend.out但代码里没有freopen。 解决在main函数开头加freopen(friend.in,r,stdin); freopen(friend.out,w,stdout);。注意文件名是相对路径评测时源文件就在对应题目目录下所以直接用文件名就行不要加路径前缀。4.3 scanf/printf 和 cin/cout 混用导致缓冲出错现象使用cin读入、printf输出或者反过来部分数据丢失或顺序错乱。 原因scanf/printf和cin/cout使用不同的缓冲机制混用后可能导致未同步。 解决要么统一用scanf/printf要么统一用cin/cout并加上ios::sync_with_stdio(false)。竞赛题一旦出现“输入输出数据比较多”的提示建议直接用scanf/printf。4.4 好朋友的边界把 x 号房也算进去现象样例都过了换一组数据就错。 原因题目明确说不包括小A的房子但有些人在循环里没有跳过ix导致把x号房当成可买。 解决在判断条件中明确写if (i x) continue;。还要注意Pi0不可卖Pim买不起这两个条件也要同时满足。我见过有人只写了价格大于0忘了资金限制输出结果比答案大。4.5 粉刷匠的时间戳比较方向写反现象蓝色格子数比预期多或少。 原因行决策的条件是“行时间 列时间”但有人写成“”或者“列时间行时间”导致覆盖关系反了。 解决用样例1手算一遍第一次刷第1行蓝色第二次刷第2列蓝色最终蓝色格子是(1,1)、(1,2)、(2,2)。用程序输出中间rt/ct数组对照检查。记住后刷的覆盖先刷的所以晚的时间戳决定颜色。5. 把真题变成自己的题库验证与改编技巧5.1 用随机数据生成器做对拍拿到题不要只靠样例题。我习惯写一个生成器生成随机小数据然后用暴力程序跟优化程序对拍。比如“好朋友”可以用随机n,x,m和Pi数组暴力枚举所有房子算答案“粉刷匠”可以用一个二维数组模拟所有操作算出一个暴力答案。生成器大致长这样// gen.cpp #include cstdio #include cstdlib #include ctime int main() { srand(time(0)); int n rand() % 10 2; int x rand() % n 1; int m rand() % 100 1; printf(%d %d %d\n, n, x, m); for (int i 0; i n; i) printf(%d , rand() % 101); }然后在命令行里跑gen | brute和gen | solve再用diff比较输出。注意暴力程序也要用相同方式处理输入输出。这个习惯能帮你省下大量调试时间尤其是卫星这种构造题对拍能及时发现排列生成错误。5.2 把四道题改造成新练习题这套题可以魔改成很多变体好朋友把n从100改成100000变成线性扫描扩展题改成“求第k近的可买房子”就需要排序后取第k个。统计人口把静态前缀和改成带单点修改就变成树状数组题把“不在家”改成“在家”答案变成区间和做题时注意转换。卫星把间隔序列改成斐波那契数列变成另一个构造题要求输出字典序最小的排列就需要贪心验证。粉刷匠把刷墙改成覆盖区间求最后有多少个格子被蓝色覆盖可以用线段树维护把颜色数扩展到三种统计每种颜色的格子数。改动数据范围、增加修改操作、调整统计口径都是一道新题。用这种“真题魔改”的方式训练比盲目刷题库效率高得多。从那以后我每次带学生刷这套题都强制他先把四道题的题意用一句话复述出来再谈代码。因为信息学竞赛最怕的不是不会算法而是没读懂题。希望帮到你。本文还有配套的精品资源点击获取