少儿信息学竞赛复赛试题解析：枚举、前缀和与逆向思维

简介绍兴市第十八届少儿信息学竞赛复赛试题文档面向小学阶段参加信息学竞赛的学生及辅导教师用于熟悉复赛题型、检验算法与程序设计基础。压缩包仅含1个docx文件大小约32KB完整收录题目一览、比赛目录结构示例、特别提醒及四道正式赛题便于按官方格式开展模拟训练。四题分别为“好朋友”“统计人口”“卫星”“粉刷匠”覆盖数组与循环、区间统计、环状模拟、行列染色等知识点并附输入输出文件名、测试点时限、分值、样例解释和数据范围可帮助读者理解命题方式、训练文件读写与边界处理。已有815人学习适合需要系统刷题、教师组卷或赛前查漏补缺的读者参考。1. 一份复赛试题就像一张体检单孩子学了一年编程家长把一份市级少儿信息学竞赛的复赛试题打印出来翻两页就愣住了代码没几行故事倒不少——买房子、统计人口、卫星编排、粉刷墙面看着更像小学奥数附加题。可它偏偏叫“信息学竞赛复赛试题”。这名字听着唬人说白了就是初赛过关之后让选手坐下来把完整程序写出来的那张卷子给定输入格式和输出格式给定时限和数据规模交上去的是能被机器自动判分的源程序而不是手算的答案。这类复赛试题最有意思的地方在于四道题像四项体检指标恰好把“这个领域到底在考什么”摊开给你看。2. 题面里为啥总要先讲个故事外衣、内核与输入输出合同2.1 从“幸福村买房”到“数轴上找一个最近的合法点”先看第一题。题面讲的是小 A 住幸福村村里 n 套房排成一条直线相邻两套隔 10 米小 A 住 x 号。小 B 想买一套离小 A 最近的房但每套房有价格 PiPi 等于 0 表示不卖小 B 手里只有 m 元。问能买到的房子离小 A 家最近多少米。这一大段故事真正进入程序的部分其实只有一句话——在编号 1 到 n 的直线上找一个位置 i满足 i 不等于 x、Pi 大于 0、Pi 不超过 m让 |i − x| × 10 最小。小 A、小 B、幸福村这三个名字在代码里一个都不会出现。这就是竞赛题的第一层功力用生活场景包装一个数学模型。包装不是废话它决定了你要不要额外处理某个条件。比如“Pi 0 表示该房不可卖”这句话翻译成代码就是一条判断p[i] 0时跳过而不是“这房子免费送”。几年前的比赛里多的是把 0 元当成免费房、开开心心输出 0 的选手。同一个题面不同的人读出不同的模型分差就从这里开始。下面这张表把四道题的外衣和内核摆在一起看会更直观题面里的说法程序里对应的东西幸福村 n 套房、相邻 10 米下标 1 到 n 的数组距离等于下标差乘 10房价 PiPi 等于 0 表示不卖数组元素同时充当判断条件小 B 的资金 m 元一个价格上限阈值编号 x 到 y 的人家不在家一段区间 [x, y] 的查询n 行 m 列的白墙、整行整列刷二维平面上的一次覆盖操作卫星排成环、间隔若干颗环形结构 跳跃规则做题时养成一个习惯读完题先在纸边写两行一行写“数据结构长什么样”一行写“要执行什么操作”。写不出来说明题还没读懂写得出来剩下的就是码代码。2.2 输入输出合同文件名、目录、格式一个标点都不能错这份试题的第二部分专门讲目录结构很多第一次参赛的人会直接跳过然后在这一步栽跟头。规定是这样的每道题建一个以英文题目名命名的目录比如好朋友叫 friend、统计人口叫 people、卫星叫 star、粉刷匠叫 paint选手把自己写的源程序放进对应目录最后把整棵目录树一起交上去只交源程序不交编译出来的可执行文件。为什么要这么死板因为判分是机器干的。机器不认你的文件夹叫“新建文件夹(2)”它只按约定的路径去找 friend 目录下的源文件找不到就是 0 分。同理程序要从 friend.in 读数据、往 friend.out 写结果你写成从键盘读、往屏幕打本地跑得再顺交上去也是白卷。这就是所谓“输入输出合同”题目给的输入格式是甲方要求输出格式是交付标准文件名是快递地址。三者缺一货就送不到。新手最常见的翻车方式不是算法写错而是多输出了一句“请输入 n 的值”或者每个答案后面多打一个空格——机器逐字符比对多一个字符就算错。提示比赛前把四道题的文件名、目录名抄在草稿纸最上面写完一题就对一遍比事后检查十遍都管用。2.3 数据范围是出题人给的台阶也是难度的刻度线每道题最后都有一栏“数据范围”初学者往往一扫而过其实这是整张卷子信息密度最高的地方。统计人口这题写得很清楚30% 的数据 n、m 都不超过 10050% 的数据 n 不超过 1000、m 不超过 10000100% 的数据两者都到 50000。这不是凑字数这是出题人明明白白告诉你暴力能拿三成分稍微优化能拿五成分想拿满得换思路。粉刷匠更直接30% 的数据行列和操作次数都不超过 1000另 30% 的数据行数不超过 10 但列数和操作数到十万100% 的数据三者都到一百万。三个档位对应三种完全不同的解法出题人等于把解题路线图铺在你面前了。于是读题顺序应该反过来先看数据范围再回头看问题描述。范围告诉你算法复杂度上限描述告诉你具体做什么两头一夹思路就很难跑偏。3. 四道题拆开看枚举、前缀和、环形构造、倒着做3.1 好朋友把最笨的枚举写对就是满分这题的数据规模是 n 不超过 100意味着什么意味着你可以把所有房子挨个看一遍一只不漏总共才一百次判断。这种“把所有可能性都试一遍”的思路叫枚举是所有算法里最朴素、也最不容易出错的一种。关键在于三个过滤条件要写全不能是小 A 自己家、房子必须卖价格不为 0、价格不能超过预算。三个条件缺一个答案就会偏。// 好朋友枚举每一套房筛出能买且最近的 int n, x, m; cin n x m; for (int i 1; i n; i) cin p[i]; int best INT_MAX; // 用一个足够大的数当初始答案 for (int i 1; i n; i) { if (i x) continue; // 排除小 A 自己家 if (p[i] 0) continue; // 0 表示不卖不是免费 if (p[i] m) continue; // 买不起 best min(best, abs(i - x) * 10); // 下标差乘 10 才是米数 } cout best endl;代码里四个参数值得单独说一句。i x这个判断对应题面括号里那句“不包括小 A 的房子”很多人第一遍会漏p[i] 0是语义陷阱不是数值陷阱p[i] m是预算约束abs(i - x) * 10是把“房号差”换算成“米”因为题面明确说相邻两套相隔 10 米。四个条件各司其职少一个都拿不到分。这题还藏着一个思维习惯先把最笨但正确的解法写出来再考虑优化。很多人一上来就想“从 x 往两边扩展谁先满足条件就是谁”思路没错但代码里要处理越界、要判断两边谁更近反而容易写错。n 只有 100 的时候老老实实枚举全部代码短、逻辑直、几乎不可能错。3.2 统计人口前缀和是区间求和的万能钥匙第二题问的是n 户人家各有若干人来 m 次询问每次告诉你编号 x 到 y 的人不在家问还能核查到多少人。翻译一下总人口减去区间 [x, y] 的人口和。最直接的做法是每次询问都从 x 加到 y一次询问最多扫五万户五万次询问就是二十五亿次加法。电脑一秒大概能跑一亿次简单运算这个量级妥妥超时。前缀和的思路很像记账与其每次问“这三个月花了多少”都翻一遍账本不如每个月月末记一个“累计到今天一共花了多少”。下次再问用后一个累计数减前一个累计数一次减法就出结果。具体做法是预处理一个数组 ss[i]表示前 i 户人家的总人口。那么区间 [x, y] 的人口和就是s[y] - s[x-1]答案就是s[n] - (s[y] - s[x-1])。// 统计人口预处理前缀和每次询问 O(1) 出答案 long long s[N]; for (int i 1; i n; i) { scanf(%d, a[i]); s[i] s[i - 1] a[i]; // 前 i 户的累计人口 } while (m--) { int x, y; scanf(%d%d, x, y); long long gone s[y] - s[x - 1]; // 不在家的那一段 printf(%lld\n, s[n] - gone); // 总人口减去这一段 }参数上要注意两处。一是s[0]要默认为 0这样 x 等于 1 时s[x-1]才成立这就是数组从下标 1 开始存的好处二是累加用long long虽然题目保证答案不超过 32 位整数范围但中间计算养成用长整型的习惯能省掉一类莫名其妙的错误。题面末尾那句“输入输出数据比较多建议用 scanf、printf”是出题人给的免费情报后面还会专门讲。3.3 卫星顺着难倒着填空反而简单第三题是整张卷子里最绕的。n 颗卫星排成一个环接收规则是先收 1 号然后间隔 1 颗卫星收到的是 2 号再间隔 2 颗收到 3 号再间隔 3 颗收到 4 号……每次间隔的数量等于上一次刚收到的那颗卫星的编号。已经收过的卫星不再计数。题目要求你反过来设计环上的排列顺序让接收顺序恰好是 1 到 n。题面给的例子是 5 颗卫星排列为 1 3 2 5 4按规则走一遍正好收到 1、2、3、4、5。顺着模拟很难因为你手上的环还没定下来。但换个方向想既然接收顺序已经定死是 1、2、3、4、5那不如按编号一个个往环上的空位里填——先决定 1 号站哪个位置再根据规则推出 2 号该站哪一步步填满。规则换个说法就清楚了填好编号 k 之后从它现在的位置出发沿着环往前走数够 k 个还没填号的位置跳过去落在下一个空位上那里就是 k1 号的位置。拿 5 颗卫星走一遍位置 1 放 1 号从位置 1 出发跳过 1 个空位位置 2落在位置 3放 2 号从位置 3 出发跳过 2 个空位位置 4、5落在位置 2放 3 号从位置 2 出发跳过 3 个空位落在位置 5放 4 号剩下位置 4 给 5 号。排出来是 1 3 2 5 4和样例一模一样。// 卫星按编号 1..n 依次找空位填进去 int pos 1; ans[1] 1; filled[1] true; // 位置 1 放 1 号 for (int k 1; k n; k) { // 已知 k 号的位置去定 k1 号 int cnt 0; while (cnt k) { // 跳过 k 个还没填号的位置 pos pos % n 1; // 环形前进一格 if (!filled[pos]) cnt; } do { // 再往前走找到下一个空位 pos pos % n 1; } while (filled[pos]); ans[pos] k 1; filled[pos] true; }pos % n 1是环形数组的标准写法n 等于 5 时位置 5 往前走一格会回到 1。filled数组记录哪些位置已经放好编号cnt记录这一轮跳过了几个空位。这段代码的复杂度是平方级n 到一万时勉强能过真要提速可以换成链表或者树状数组但那是另一层优化先把构造逻辑想明白更重要。这题真正考的不是代码是能不能把“接收规则”翻译成“填空规则”。同一个过程正着描述和反着构造难度差了一个量级。3.4 粉刷匠最后一次刷的颜色才说了算第四题一面 n 行 m 列的白墙每次把整行或整列刷成红色或蓝色一共刷 k 次问最后有多少个格子是蓝色。数据规模最大到一百万行列和操作次数都是。正着做几乎没法做。一百万乘一百万是一万亿个格子光开数组就爆内存更别说逐格染色。可换个角度一个格子最终是什么颜色取决于最后一次刷到它的那一下。既然如此从最后一次操作往回倒着看某一行第一次在倒序里出现这次操作就决定了这一行上所有还没被列操作覆盖的格子之后再遇到同一行的操作全是无效的。这就是逆向思维与其追踪每个格子被刷了几次不如判断每次操作“能管到多少还没被覆盖的格子”。// 粉刷匠倒序扫描每次操作只结算还没被覆盖的格子 long long ans 0; int restRow n, restCol m; // 还没被任何操作“认领”的行数和列数 for (int i k; i 1; --i) { int x op[i][0], y op[i][1], z op[i][2]; if (x 0) { // 刷的是第 y 行 if (rowDone[y]) continue; // 这一行已经被后面的操作覆盖过 rowDone[y] 1; --restRow; if (z 1) ans restCol; // 蓝色贡献剩下未被列覆盖的格子 } else { // 刷的是第 y 列 if (colDone[y]) continue; colDone[y] 1; --restCol; if (z 1) ans restRow; } }rowDone和colDone记录某行某列是否已经被“认领”restRow和restCol是还没被认领的行列数量。刷一行蓝色时它能染蓝的格子数正好等于此刻还没被列操作覆盖的列数也就是restCol。刷红色则一格蓝色都不贡献直接跳过。整段代码只扫一遍操作序列复杂度是线性的一百万次操作轻松跑完。拿题面第一个样例验证两行两列先刷第 1 行蓝色再刷第 2 列蓝色。倒序先看第 2 列此刻restRow 2蓝色贡献 2再看第 1 行此刻restCol 1蓝色贡献 1加起来是 3与样例一致。第二个样例把第二次改成刷红色倒序看红色不贡献最后只剩 1也一致。这题是整张卷子里最能体现“想清楚再动手”的一道。代码不到二十行但能不能想到倒着看决定了你是十分钟写完还是四十分钟卡死。4. 一秒钟到底能算多少次时限、常数与数组边界4.1 把“1 秒”翻译成复杂度题面每道题都标了时限前三题 1 秒粉刷匠 2 秒。这个数字不是装饰它是一条硬杠杠程序跑超了答案再对也判零分。经验上的换算关系大概是一秒内普通电脑能完成一亿次左右的简单运算加法、比较、赋值这类。保守一点按一千万算比较稳妥。于是有了这张对照表数据规模能承受的复杂度常见做法n 不超过 100三重循环也没问题纯枚举逐层试n 不超过 1000平方级双重循环简单模拟n 不超过 50000线性或线性乘对数前缀和、排序、双指针n 到一百万只能扫一两遍一遍扫描、倒序处理有了这张表再回头看统计人口n 和 m 都是 50000平方级是二十五亿次明显超线性是一万次预处理加五万次查询轻松。粉刷匠 n、m、k 都是一百万任何带“每行每列都扫一遍”的做法都会爆只有一遍扫描的倒序法能活。这里要说清楚一点复杂度是量级判断不是精确计时。同样是一亿次循环里面做的是加法还是取模速度能差好几倍用的是数组还是哈希表差别更大。所以看到“刚好卡在边界”的规模宁可多降一档。4.2 为什么题面反复叮嘱用 scanf 和 printf统计人口和粉刷匠两道题的末尾出题人都加了一句“输入输出数据比较多建议用 scanf、printf”。这不是客套话。用 C 的 cin 和 cout 读写时默认会和 C 语言的输入输出保持同步这个机制保证混用不出错代价是速度慢好几倍。数据量小的时候感觉不出来一旦要读几十万、上百万个数光是读入就能吃掉大半秒。两个解决办法一是改用 scanf 和 printf二是保留 cin但在程序开头加两行ios::sync_with_stdio(false); // 解除与 stdio 的同步 cin.tie(0); // 解除 cin 与 cout 的绑定这两行是竞赛里的常见配置作用是把 cin 的额外开销关掉。关掉之后速度能提上来但就不能再混用 scanf 和 cin 了读入方式要统一。这件事说明一个常被忽略的道理超时不一定是算法错也可能是常数太大。算法复杂度是一回事每步操作实际花多少时间又是另一回事。同一份逻辑读入方式换一下可能就从超时变成通过。4.3 数组开多大才不至于“玄学”报错数组开小了是新手最常见的隐形坑。题面说 n 不超过 50000很多人就写int a[50000]结果程序用到下标 50000 时越界把隔壁变量的值覆盖掉了。表现出来就是样例过、逻辑对、部分测试点莫名其妙出错查半天查不出来——这种事在赛场上属于典型的玄学。规矩很简单开数组时多留几个位置。数据规模是 n就开a[n 5]或a[n 10]因为多数人习惯从下标 1 开始存下标 0 空着末尾再留点余量给循环里的i 1。另一个坑是内存。一个 int 占 4 字节一百万个 int 是 4MB一千万个是 40MB常见的内存限制是 256MB。粉刷匠要是真按题意开一个一百万乘一百万的二维数组那是四万亿字节程序还没开始跑就被系统掐了。遇到这种规模就得改数据结构——只存 k 次操作不存整面墙。判断标准也很朴素先估一遍“我要存多少个东西每个多大”乘以 4 或者 8跟内存限制比一比。超了就说明思路得换。5. 五个最容易混淆的概念信息学竞赛不是编程课5.1 信息学竞赛和少儿编程课不是一回事易混点都叫“学编程”都有老师在讲台上演示都要在电脑上敲东西。为什么混入门阶段两者确实重合都是从“输出一句话”“算个加法”开始。家长看到孩子能做出一个小动画就觉得竞赛也能应付。怎么区分编程课的目标通常是“做出效果”拖积木能让小猫走起来就算成功竞赛的目标是“在限制内算对”代码要交给机器用几十组甚至上百组数据去测错一组就扣分。前者关心创意和完成度后者关心正确性和效率。这份复赛试题里没有一道题问“界面好不好看”全是问“输出这个整数是多少”。5.2 文件输入输出和标准输入输出别混着用易混点平时练习都是从键盘输入、屏幕上打印而这份试题的四道题都规定了输入文件名和输出文件名比如 friend.in、friend.out。为什么混本地调试时有些人直接在终端里手敲数据程序照样跑出结果于是以为大功告成。交上去却是零分因为判分程序是把数据写进 friend.in再从 friend.out 里读答案你的程序压根没碰这两个文件。怎么区分看题面的“输入文件名”和“输出文件名”两栏。写了具体文件名就在程序开头用 freopen 把标准输入输出重定向到文件写的是“标准输入”才从键盘读。最稳妥的办法是赛前跟监考确认一遍评测方式别靠猜。这类失误丢的分最冤因为代码本身是对的。5.3 样例通过只等于语法检查通过易混点题面给了两组样例输入进去输出对上了就认为这题做完了。为什么混样例是出题人特意挑的、能手算出来的小数据它的作用是帮你确认“输入格式理解对了、输出格式没多打空格”。它证明不了你的算法在所有情况下都对。怎么区分把“过样例”当成“编译通过”的同义词而不是“逻辑正确”的同义词。真正的验证要看数据范围里的边界n 取最小值 2 时对不对、x 在两端时对不对、所有房子都买不起时对不对、全刷同一行时对不对。这些情况样例一个都没覆盖偏偏测试点里全是。老手写完题会自己造几组极端数据跑一遍这个习惯比多刷十道题都值钱。5.4 暴力枚举不等于拿不到分易混点一听“暴力”两个字就觉得是笨办法、是低分方案必须想个高级算法才配叫解题。为什么混教程里讲暴力往往带着贬义动不动就是“这样会超时我们要优化”。怎么区分看数据范围。好朋友这题 n 不超过 100标准解法就是枚举写得越直白越安全统计人口的前 30% 数据 n、m 都不超过 100暴力同样能拿满这三十分。暴力是正解还是部分分取决于规模不取决于它听起来高不高级。真正该练的能力是看到范围就能判断“这个规模下暴力够不够”而不是一上来就追求花哨。5.5 代码短不等于题目简单易混点粉刷匠的逆序解法不到二十行比很多课后练习还短于是有人觉得这题是送分题。为什么混习惯用代码行数衡量难度行数少就是简单行数多就是难。怎么区分难度在“想到”不在“写下”。粉刷匠难在你要意识到“只有最后一次染色有效”从而把正向模拟翻转成倒序结算卫星难在要把“接收规则”翻译成“填空规则”。这两步想通了代码都很短想不通写一百行也白搭。反过来有些题代码又长又繁琐但每一步都是套路反而好拿分。判断一道题难不难看的是建模和复杂度这两关不是看键盘敲了多少下。6. 什么时候该拿这份试题练手什么时候先放一放6.1 三类人适合三类人不适合判断标准不是年龄是手上有没有那几样基本功能不能独立写出循环和数组能不能看懂“输入格式”那几行字能不能把一个生活问题翻译成“对什么数据做什么操作”。你的状态适不适合原因已能独立写出完整程序想检验读题到编码的整条链路适合四道题覆盖枚举、前缀和、构造、逆向四种典型套路准备参加区级或市级比赛想熟悉题型和目录规范适合题面里的文件命名、目录结构就是真实比赛的样子想练“先看数据范围再选算法”的习惯适合每道题都有分档数据正好对照着判断复杂度刚学图形化编程还没手写过完整代码不适合会被文件读写和数组下标劝退先补基础更划算只想靠背题应付初赛不适合四道题的解法各不相同背下来也迁移不了已经能稳定做出提高组难度的题不适合这套题偏入门练手价值有限不如找更复杂的题6.2 一个具体的使用顺序真要用这份卷子练别按题号从一做到四。先花十分钟只读题不写代码在纸上给每道题标两件事数据结构长什么样、数据范围允许什么复杂度。标完再对照第 4 章那张表看看自己的判断对不对。然后从好朋友本文还有配套的精品资源点击获取