简介第十八届绍兴市少儿信息学竞赛复赛试题以docx文档形式打包面向小学阶段参与NOIP类信息学竞赛的选手可作为编程入门与竞赛实战的练习材料。压缩包内为一个docx文件大小约为32KB包含“好朋友”“统计人口”“卫星”“粉刷匠”四道完整赛题每道题均给出问题描述、输入输出格式、样例解释及数据范围并附比赛目录结构示例便于模拟真实考场要求。其中“好朋友”重点考查数组与循环“统计人口”可用前缀和或数据结构优化“卫星”要求模拟环状跳跃过程“粉刷匠”需要处理行列覆盖的计数问题能够综合训练读题建模、算法设计、边界处理与调试能力。目前已有812人学习下载适合需要熟悉绍兴赛区命题风格、独立完成限时模拟训练的师生使用。1. 一份复赛试题文档为什么值得反复读三遍看到「第18届绍兴市少儿信息学竞赛复赛试题.docx」这个文件名先别急着找答案或解析这份文档更准确的定位是一面镜子。它映照的不是某一道题的解法而是这个年龄段选手在算法思维上的真实分水岭四道题、三小时、从模拟到搜索再到动态规划的梯度设计每一题都在筛选不同层级的计算思维。这篇文章不猜题、不押题只讲一件事——拿到一份复赛试题文档后怎么通过拆题、复现、避坑、归因把它变成一条看得见进步的训练路径。适合三类人准备参赛的小学生家长、带竞赛队的入门教练、以及想自测水平的选手本人。请把这份 docx 当作训练标本而不是一次性的考试纪念品。2. 复赛试题的结构与难度梯度先看懂考察什么再动手2.1 四道题的标准配比与时间分配市级少儿信息学竞赛的复赛通行做法是四道编程题、三个小时、全程上机编程语言以 C 为主。四道题有明确的难度分工接近一套固定的配方第一题是签到题考查输入输出和基础模拟目的是让大部分选手拿分、建立信心第二题开始引入算法思想通常是简单的贪心或二分第三题进入中档常见组合是稍复杂的模拟或基础动态规划第四题是压轴多半是搜索剪枝、区间 DP 或带优化的状态转移用来拉出区分度。题号常见定位典型考察点目标得分人群T1签到题顺序结构、循环、简单模拟全体选手T2基础算法贪心、二分答案、桶计数训练半年以上选手T3中档题二维模拟、基础 DP、DFS系统训练过的选手T4压轴题搜索优化、背包变种、区间 DP冲一等奖选手拿到试题后第一件事不是看题面而是先把四道题的数据范围列成一张表。这个动作能让你在 10 分钟内判断出每道题的期望算法也直接决定你后面三个小时的时间预算。我一般按「10 分钟读题划范围 → 40 分钟攻克 T1 T2 → 70 分钟啃 T3 → 剩余时间做 T4 并回头检查」的节奏走切忌在 T4 上死磕超过 40 分钟。2.2 从题面表述推断考察点的三条线索少儿信息学竞赛的题面不会直接告诉你「这题用 DP」但会留下三条明显的线索。第一条是操作类型题面出现「移动、交换、转换、按规则生成」这类动词优先考虑模拟出现「最小、最大、至少、最多」这类最值表述基本锁定贪心或二分答案出现「方案数、多少种走法、最优值」且带有明显的阶段递进就要往动态规划方向想。第二条是数据范围n ≤ 20 暗示状压或暴搜n ≤ 10^5 暗示 O(n log n) 算法n ≤ 10^9 则基本只能 O(log n)。第三条是输出要求只输出一个数往往对应最值类问题要求输出具体路径或方案就要准备记录前驱或回溯。这三条线索在复赛里是叠加使用的。比如一道题数据范围写着 n ≤ 10^5又要求「最小花费」你可以放心地先假设是二分答案再设计一个 O(n) 的 check 函数验证。如果题面里能拆出「前 i 个」「第 i 天」「前 i 种物品」这类状态前缀动态规划的概率就超过八成。把这些判断写成一张小纸条贴在电脑边框上做题时每看一题就对着过一遍能少走很多弯路。3. 从试题到可复现代码四类题型的 C 落地模板3.1 模拟题先画状态机再写循环复赛第一题几乎必考模拟。这类题没有算法门槛拼的是「读题仔细、状态完整」。我见过大量选手在模拟题上翻车原因不是不会写循环而是漏掉了题面里某个边界条件。写模拟题的正确顺序是先不碰键盘用纸笔把题面描述的过程画成状态转移图标出每个状态的输入和输出再开始编码。#include bits/stdc.h using namespace std; int main() { // 假设题面模拟一个机器人按指令移动的过程 int n, x 0, y 0; cin n; string cmd; for (int i 0; i n; i) { cin cmd; if (cmd UP) y; // 向上 else if (cmd DOWN) y--; // 向下 else if (cmd LEFT) x--; // 向左 else if (cmd RIGHT) x; // 向右 else { // 兜底分支处理题面中的特殊指令 // 常见坑题目可能有“重复上一次指令”这类描述 cerr unknown command endl; } } cout x y endl; return 0; }这段代码的逻辑核心是维护一个坐标状态每读一条指令就更新一次。这里有两个关键点第一所有可能的分支都要走 if-else 链覆盖不能漏掉题面里看似无关紧要的补充描述第二cerr 输出在竞赛评测里不会计入答案只用于本地调试放心使用。如果题面出现「重复上一次指令」你需要在循环外面单独用一个变量记录上一条有效指令而不是在当前分支里直接处理。模拟题的通用优化手法是省去 vector 和 map直接用数组下标做映射。方向类模拟可以用两个数组 dx[4] {0, 0, -1, 1} 和 dy[4] {-1, 1, 0, 0} 配合方向编号这样写出来的代码既短又不容易错。记住模拟题的目标不是写得漂亮而是把每一个 if 分支都对上题面的一句话。3.2 二分与贪心用 check 函数统一处理极值问题第二题的常见面孔是「最小化最大值」或「最大化最小值」。这类题的通用解法是二分答案把极值问题转化为判定问题。核心技巧是抽象出一个 check(mid) 函数判断在当前答案 mid 下题目要求是否可行然后根据可行性收紧二分边界。#include bits/stdc.h using namespace std; int n; vectorint a; // 输入数组 int m; // 需要分成的段数 // check 函数能否让“每段和的最大值”不超过 x bool check(int x) { int cnt 1, cur 0; for (int i 0; i n; i) { if (a[i] x) return false; // 单个元素超限直接不可行 if (cur a[i] x) { // 当前段放不下开新段 cnt; cur a[i]; } else { cur a[i]; } } return cnt m; // 分段数不超过 m 则可行 } int main() { cin n m; a.resize(n); int sum 0, mx 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; mx max(mx, a[i]); } int lo mx, hi sum; // 下界是最大值上界是总和 while (lo hi) { int mid (lo hi) / 2; if (check(mid)) hi mid; else lo mid 1; } cout lo endl; return 0; }check 函数是二分的灵魂。它的返回值要严格对应题目语义是「能不能做到」而不是「最优值是多少」。这个例子里 check(x) 的作用是判断在每段和不超过 x 的前提下能否用不超过 m 段装下所有元素边界下界取数组最大值、上界取数组总和是因为答案不可能小于单元素最大值、也不可能大于总和。用这种写法处理各种「最大值最小化」问题只需要改 check 函数的内部逻辑外层二分模板完全不用动。二分时有一个必须注意的细节mid 的取法和边界更新方向要配套避免死循环。惯例是下界能取到答案时用 mid (lo hi) / 2配合 hi mid上界取不到时用 mid (lo hi 1) / 2配合 lo mid。很多选手直接套模板翻车根本原因就是这里的 1 没加对。3.3 简单动态规划先写转移方程再想优化动态规划是复赛第三题的常客也是区分度最大的知识点。写 DP 题最忌讳拿到题就开数组正确流程是先用纸笔推导状态定义、转移方程和边界条件全部明确后再写代码。少儿组的 DP 题通常不会出状态压缩和斜率优化但会考「从暴力递归改成记忆化」的能力。#include bits/stdc.h using namespace std; int dp[1005][1005]; int w[1005], v[1005]; int main() { // 0/1 背包n 件物品容量 m每件物品只能用一次 int n, m; cin n m; for (int i 1; i n; i) { cin w[i] v[i]; } for (int i 1; i n; i) { for (int j 0; j m; j) { // 不取第 i 件 dp[i][j] dp[i-1][j]; // 取第 i 件前提是容量够 if (j w[i]) { dp[i][j] max(dp[i][j], dp[i-1][j-w[i]] v[i]); } } } cout dp[n][m] endl; return 0; }这个经典的 0/1 背包模板有三个参数要理解透彻第一dp[i][j] 表示「从前 i 件物品中选、总容量不超过 j 的最大价值」这个状态定义直接决定了转移方程怎么写第二取第 i 件物品时前 i-1 件物品占用的容量是 j-w[i]所以要从 dp[i-1][j-w[i]] 转移过来第三for 循环里容量 j 从 0 到 m 的顺序在二维写法下无所谓但如果优化成一维滚动数组j 就必须倒序枚举否则同一件物品会被重复取用。少儿组 DP 题的常见变体是从「选或不选」扩展成「选几个」比如完全背包。处理方式是把内层循环改成「枚举第 i 件物品取 k 件」但这样是 O(n * m * k)很容易超时。更优雅的做法是正序枚举容量让同一件物品可以多次转移。这就是「先写出朴素转移方程再观察循环方向能不能优化」的典型范例也是复赛第三题和第四题的分界点。3.4 搜索题DFS 与 BFS 的选择边界压轴题里搜索永远占有一席之地。很多选手对搜索有误解觉得它是暴力、是无奈之举但竞赛里搜索的正确用法是「剪枝之后的精准枚举」。DFS 适合求可行路径、排列组合、连通性判断BFS 适合求最短步数、最少操作次数。选择依据很简单如果答案路径的深浅不定用 DFS 加剪枝如果每步代价相同且要最短路径用 BFS。#include bits/stdc.h using namespace std; char grid[105][105]; int vis[105][105]; int n, m; int dx[4] {0, 0, -1, 1}; int dy[4] {-1, 1, 0, 0}; // 从 (sx, sy) 开始 BFS返回能否到达终点 bool bfs(int sx, int sy, int ex, int ey) { queuepairint, int q; q.push({sx, sy}); vis[sx][sy] 1; while (!q.empty()) { int x q.front().first, y q.front().second; q.pop(); if (x ex y ey) return true; for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; // 越界和障碍判断 if (nx 1 || nx n || ny 1 || ny m) continue; if (grid[nx][ny] # || vis[nx][ny]) continue; vis[nx][ny] 1; q.push({nx, ny}); } } return false; }BFS 这段代码里最值钱的参数是 vis 数组它不只是防止走回头路更是保证队列里每个点最多入队一次从而把复杂度控制在 O(n*m)。边界判断 four continue 的顺序有讲究先判越界再判障碍再判访问标记这个顺序能避免数组下标越界访问。少儿组的搜索题地图通常不超过 100×100这种写法完全够用。如果要改成 DFS核心变化是把队列换成递归并在回溯时重置 vis。DFS 的难点在剪枝用「当前步数 到终点的曼哈顿距离是否超过已知最优解」这种乐观估计来提前终止。记住竞赛评测看的是程序在数据范围内的表现搜索题能拿满分的选手赢在剪枝而不在枚举。4. 数据范围与评测环境把参数读准比多写代码更值钱4.1 数据范围决定算法复杂度先读数据再选题型我见过太多选手拿到题就写代码写完才发现算法复杂度不对白白浪费一个小时。正确做法是先把每道题的「时间限制、空间限制、数据范围」抄在草稿纸上再用这张表决定算法。数据规模可接受的时间复杂度推荐算法方向n ≤ 20O(2^n)状压枚举、暴力搜索n ≤ 500O(n^3)三重循环动态规划、Floydn ≤ 5000O(n^2)双层循环 DP、朴素 Dijkstran ≤ 10^5O(n log n)二分、排序、线段树、堆n ≤ 10^6O(n)前缀和、双指针、单调队列n ≤ 10^9O(log n)数学公式、快速幂、二分这张对照表的背后是「1 秒大约能运行 10^8 次简单操作」这个经验值。看到 n ≤ 10^5你第一反应应该是「这题不允许 O(n^2)」而不是「这题很复杂」。少儿组复赛的数据范围通常留了情面题目敢开 n ≤ 5000就说明它想考你优化过的 O(n^2) 甚至 O(n log n)但不会让你必须用高级数据结构才能过。读数据范围时要特别警惕「多组数据」这个隐藏条件。有些题面写着 T 组测试数据单组 n ≤ 10^4但你没乘 T实际复杂度瞬间爆炸。我习惯在草稿纸上把 T * n 的总量算出来用它去和上面的对照表比对而不是只看单个 n。4.2 文件读写与评测目录的固定写法少儿信息学竞赛复赛基本沿用统一的评测方式程序从指定的 .in 文件读入向指定的 .out 文件输出。这一条写不对代码逻辑再对也是零分。固定写法是在 main 函数的第一行加 freopen考试时直接套用。#include bits/stdc.h using namespace std; int main() { // 注意这里的 match.in 换成题目实际要求的文件名 freopen(match.in, r, stdin); freopen(match.out, w, stdout); int a, b; cin a b; cout a b endl; return 0; }freopen 的两个参数分别指定读入文件和输出文件一旦设置了就会把标准输入输出全部重定向。参数说明第一个参数是文件名必须与题目要求完全一致大小写、后缀都不能差第二个参数 r 表示读、w 表示写评测系统只看你往 .out 文件里写了什么。本地调试时如果不想每次改文件可以在代码里加一个 DEBUG 宏生产环境用 freopen本地输出到屏幕。写文件读写的三条铁律第一文件名以题目给的为准绝不自己改名第二freopen 必须放在任何 cin/cout 之前否则重定向不生效第三程序结束时可以不主动 fclose评测会自动回收但养成习惯关掉也无妨。很多选手本地编译正常、一交上去零分八成就是 freopen 拼错了文件名。4.3 时间限制与空间限制的真实含义复赛的时间限制通常是每道题 1 秒到 2 秒空间限制 128MB 或 256MB。时间限制的有效含义不是「代码要跑得多快」而是「你的算法在最坏数据下不能超时」。评测系统会在所有测试点上运行你的程序任何一个点超时整个题目的分数都受影响部分评测机还会按测试点给部分分。空间限制换算成实际数据结构时有一个常用估算值一个 int 占 4 字节256MB 大约能开 6700 万个 int。实际做二维 DP 时如果 n 是 5000开 5000×5000 的 int 数组是 100MB刚好卡在限制内如果开 long long 就变成 200MB直接爆。所以赛场上要养成看数据范围先算内存的习惯。这里给一个保命建议头文件里的数组尽量开成全局变量而不是在函数内部定义。全局变量分配在静态区不会让栈溢出函数内的局部大数组很容易爆栈导致「段错误」而这类错误的报错信息在竞赛评测里非常隐晦常常显示「运行时错误」让你摸不着头脑。5. 避坑复赛翻车率最高的 5 个问题5.1 freopen 路径写错导致「本地能跑、评测零分」现象程序在本地任意路径下运行都正常换到评测系统上全部测试点输出「文件未找到」或直接零分。原因stdio 重定向的文件名与评测目录里的实际文件名不匹配最常见的是把 match.in 写成 match.txt 或 Match.in甚至忘记写 freopen。解决开考后第一件事是在代码里写下 freopen 两条语句文件名直接从题面复制而不是手打交卷前花一分钟把每个文件名和题目要求逐字核对一遍包括后缀和大小写。5.2 数组越界与边界判断缺失现象数据范围写着 n ≤ 100你开了 105 的数组结果运行时错误。原因题目可能存在「多组数据」或「偏移访问」的情形比如题面用 1 到 n 的下标而你只开 105当数据构造用到下标 100 时你的越界读到了非法内存。解决统一把数组多开 10 个单位的余量即 n ≤ 100 就开 110处理二维网格时下标从一开始把 0 行 0 列全部空出来作为哨兵这样既避免越界又让判断条件更简洁。数组越界是 C 里最容易踩又最不好排错的坑评测系统报「运行时错误」时第一反应就该检查数组空间。5.3 数据类型溢出导致答案错误现象样例全对测试点大面积错误而且错的基本是大数据。原因计算过程中出现了超出 int 范围的中间值。比如 n ≤ 10^5数组元素求和达到 10^10用 int 存和直接溢出为负数。解决判断「涉及累加、连乘、加法比较」的运算统一用 long long如果数据范围超过 10^18就要考虑 unsigned long long 或高精度。一个实用的检查方法是在写完关键运算后自己心算一遍最大输入下的中间结果量级大于 2^31 就换 long long。5.4 输出格式与多余空格现象逻辑完全正确但有一个测试点 WA。原因输出格式要求「每行一个数」你多输出了行末空格或者要求「答案之间用空格隔开」你用换行隔开了。评测对比是严格按字符流逐字节比对多一个空格就是错误。解决先看题目的输出描述特别是标点符号和分隔符如果是输出数组用「第一个元素前不输出空格之后每输出一个元素先加空格」的写法代替「每个元素后跟空格」的写法从根本上避免行末空格问题。这个习惯能救回至少 10 分。5.5 暴力骗分的有效姿势现象压轴题完全没思路直接空着交白卷。原因对部分分机制不敏感。复赛通常按测试点给分一个点一个点地算暴力枚举和朴素搜索往往能通过前 30% 到 50% 的数据。解决时间还剩 30 分钟时不要死磕正解立刻写一个不剪枝的 DFS 或纯暴力循环把能过的数据范围全部吃下。这些暴力代码要保证逻辑与题目完全一致只是复杂度高靠数据范围小拿分。三个小时的比赛T4 写个暴力再回头检查 T1 的边界比在 T4 上发呆到结束要划算得多。6. 把一份复赛试题用出真题集的价值限时自测与错题归因6.1 用 3 小时完整复现考场节奏升序一份试卷最大的价值就是原封不动地模拟一次复赛。找一个完整的周末上午把手机放到另一个房间桌上只留纸笔和电脑从准时开始计时三个小时完整地做一遍这四道题。过程中不要暂停、不要翻资料、不要和别人讨论一切按考场规则来。结束之后把得分统计出来这就是你当前水平最真实的一张成绩单。平时练习你可能会查资料、写写停停但这份分数能直接对标正式比赛的水位线。6.2 赛后按「丢分原因」而不是「题目对错」归因复盘阶段不要只盯着「这题我 AC 了没」而是把每题丢的分按原因归类。常见归因类别有审题偏差理解错了题意、算法错误复杂度太高或思路不对、实现失误边界/溢出/格式、时间分配失误一题耗时过长导致后面没时间。用一张表格把四道题一行一行列出来填上每题消耗时间、最终得分、丢分原因。你会发现自己的问题非常集中可能是「模拟题边界总错」也可能是「第二题总想复杂」。找到这个集中点才谈得上定向练习。6.3 隔两周重构把 AC 代码改成最优解这份试题做完一遍后不要压箱底。两周之后不看任何笔记重新做一遍但这次有更高的要求A 题强制要求压到 40 行以内B 题要求把暴力改成二分或贪心C 题要求写出滚动数组优化版D 题要求给朴素搜索加上三种剪枝。每次重构都是一次「带着新经验审视旧问题」的刻意练习。我最早带队员的时候总迷信刷题数量后来发现把一份复赛试题做三遍吃透每一题的所有解法比盲目做十套模拟题都要有效——后者只会让错误固化成习惯。这是最想让读者从这篇文章带走的经验。希望帮到你。本文还有配套的精品资源点击获取