简介这份资源是第18届绍兴市少儿信息学竞赛复赛试题文档面向备战NOIP系列赛事的小学高年级及初中信息学选手与辅导教师用于熟悉复赛题型、检验算法与编程基本功。压缩包内共1个docx文件约32KB完整收录比赛题目说明、输入输出格式、样例与数据范围约定并附有比赛目录结构与提交规范提醒。试题围绕“好朋友”“统计人口”“卫星”“粉刷匠”四道题展开分别涉及数组与循环模拟、区间统计与数据结构、环形序列构造、行列染色计数等知识点可帮助读者按题面还原评测要求练习文件读写、边界处理与复杂度控制。目前已有815人学习下载适合作为赛前模拟训练与知识点查漏补缺的参考材料。1. 四道题就是一张地图小学信息学复赛到底在考什么很多人拿到一份少儿信息学竞赛的复赛真题第一反应是“这不就是四道编程题吗”然后埋头去写代码。但真正把这份卷子从头到尾拆一遍会发现它其实是一张非常清晰的知识地图四道题分别对应四个不同的能力层级从最基础的枚举与条件判断到前缀和优化再到模拟与构造最后是逆向思维加数据规模分析。这四道题放在一起恰好覆盖了小学阶段信息学竞赛的核心考点——数组操作、循环控制、边界处理、时间复杂度的直觉判断以及“读题比写代码更重要”这条血泪经验。这份卷子适合两类人一类是正在系统学习 C 或 Pascal、准备参加区市级竞赛的学生可以用它做一次完整的自测另一类是已经学过基础语法但总在比赛中翻车的选手因为它的四道题几乎把小学组最常见的踩坑点都埋了一遍。150 分钟、四道题、每题 10 个测试点这个配置本身就值得研究——它意味着平均每题只有 37 分钟左右读题、建模、编码、调试全算进去时间分配本身就是一道隐形的题。2. 好朋友枚举与距离计算的第一道门槛2.1 题目在考什么这道题的场景很直白一条直线上有 n 套房房号 1 到 n相邻距离 10 米。小 A 住在 x 号房小 B 想买一套离小 A 最近的房子但有两个约束——不能买小 A 那套且房价不能超过预算 m。价格 Pi 为 0 表示该房不可卖。求小 B 能买到的房子离小 A 家的最近距离。核心逻辑拆开来看就三步第一遍历所有房号第二筛掉不可卖的Pi 0和买不起的Pi m以及小 A 自己那套房号等于 x第三在剩下的房里找离 x 最近的距离按 |房号差| × 10 计算。2.2 关键实现与参数说明用 C 写出来大概是这样#include cstdio #include cstdlib #include climits int main() { int n, x, m; scanf(%d %d %d, n, x, m); int best INT_MAX; // 初始化为无穷大表示还没找到 for (int i 1; i n; i) { int p; scanf(%d, p); if (i x) continue; // 不能买小A自己的房子 if (p 0) continue; // 不可卖 if (p m) continue; // 买不起 int dist abs(i - x) * 10; // 房号差乘以10米 if (dist best) best dist; } printf(%d\n, best); return 0; }这段代码里最容易被忽略的是best的初始值。如果初始化为 0后面比较dist best永远不成立答案就错了。用INT_MAX是稳妥做法但要注意题目保证至少有一套可买的房所以循环结束后best一定被更新过。另一个细节是距离计算题目说相邻房子距离 10 米房号差为 d 时距离是 d × 10不是 d。样例 1 里小 A 住 2 号可买的最近是 4 号房号差 2距离 20验证了这个公式。2.3 复杂度与数据范围的关系n 最大 100O(n) 的遍历完全够用甚至 O(n²) 都不会超时。但这道题的价值不在于复杂度而在于“多条件筛选”的编码习惯三个 continue 的顺序其实有讲究。如果先判断价格再判断房号逻辑上没问题但把i x放在最前面可以少做一次价格读取后的判断——不过这里价格已经读进来了所以顺序不影响正确性只影响可读性。梳理下来会发现这类题最稳的写法是“先排除所有不可能再在可能里找最优”而不是“边找边判断”后者容易在边界上翻车。3. 统计人口前缀和从 O(nm) 到 O(nm) 的跨越3.1 暴力思路为什么不够题目给 n 户人家的人口数m 次询问每次问“编号 x 到 y 的人都不在家能核查到多少人口”。翻译一下就是总和减去区间 [x, y] 的人口和。最直白的做法是每次询问都从 x 加到 y再拿总和去减。n 和 m 最大都是 50000最坏情况下每次询问区间覆盖整个数组总操作次数 50000 × 50000 2.5 × 10⁹1 秒时限下必然超时。这就是这道题埋的第一个坑数据范围里 30% 是 n, m ≤ 10050% 是 n ≤ 1000、m ≤ 10000只有 100% 才拉到 50000。如果只盯着小数据写暴力能拿 50 分但复赛要的是满分。3.2 前缀和的标准解法前缀和的核心就一句话预处理一个数组pre[i]表示前 i 户的总人口那么区间 [x, y] 的和等于pre[y] - pre[x-1]。每次询问 O(1)总复杂度 O(n m)。#include cstdio int a[50005]; long long pre[50005]; // 用long long防止累加溢出 int main() { 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]; // 前缀和递推 } long long total pre[n]; for (int i 0; i m; i) { int x, y; scanf(%d %d, x, y); long long away pre[y] - pre[x - 1]; // 区间和 printf(%lld\n, total - away); } return 0; }几个参数要盯住pre数组用long long因为题目说答案不超过 2³¹−1但前缀和累加过程中可能短暂超过 int 范围虽然这题人口数不大但养成习惯没坏处pre[0]默认为 0这是递推的起点不能漏区间和公式是pre[y] - pre[x-1]减的是x-1不是x这是前缀和最经典的易错点。3.3 输入输出效率的隐性考点题目末尾专门提示“输入输出数据比较多建议用 scanf、printf”。这不是客套话。m 最大 50000如果用 cin/cout 且没关同步在某些评测机上确实可能卡时限。小学组选手往往习惯用 cin这道题就是一次明确的提醒数据量上万的时候输入输出方式要纳入考虑。另外输出格式是每行一个数用printf(%lld\n, ...)比cout ... endl更稳因为 endl 会强制刷新缓冲区频繁调用有开销。4. 卫星环形模拟与构造题的思维转换4.1 题目到底在求什么这道题是四道里最绕的。它给一个 n要求设计一个 1 到 n 的环形排列使得按照特定规则接收信号时接收顺序恰好是 1, 2, 3, …, n。规则是先接收 1 号卫星然后间隔 1 颗跳过 1 颗未接收的接收下一颗再间隔 2 颗接收下一颗间隔数等于上一次接收到的卫星编号。已接收的卫星不再计数。换句话说题目不是让你模拟接收过程而是让你反推排列。这是典型的构造题正向规则已知反向求初始状态。4.2 从样例反推规律看 n 5 的样例输出1 3 2 5 4。验证一下环上顺序是 1→3→2→5→4→1。先收 1 号间隔 1 颗未接收的1 后面是 3已收不3 还没收但 1 刚收完下一个是 3间隔 1 颗意味着跳过 3这里要仔细。实际上规则里的“间隔 1 颗”指的是在未接收的卫星中数 1 颗跳过然后收下一颗。按样例的环 1,3,2,5,4收 1 后未收的是 3,2,5,4间隔 1 颗跳过 3收 2——但 2 在环上的位置是第三个说明“间隔”是在环上按物理顺序数跳过已收的不算。这个细节非常容易读错也是这道题最大的理解门槛。梳理下来构造的规律是第 k 步接收的卫星编号是 k而它在环上的位置需要满足“从上一个接收位置出发在剩余未接收卫星中数 k 颗跳过 k 颗下一颗就是 k1 号”。反推时可以用一个动态数组维护剩余卫星每次按规则插入。4.3 数据规模决定算法选择n 最大 1000050% 是 1000。如果用链表模拟插入O(n²) 在 10000 时是 10⁸ 级别勉强能过但很险更稳的做法是用树状数组或线段树维护“第 k 个未接收位置”把单次查询降到 O(log n)。不过对小学组来说O(n²) 的数组模拟每次线性扫描找第 k 个未收的在 n 10000 时大约 5000 万次操作C 下 1 秒内通常能跑完属于“能过但不优雅”的解法。这道题真正的难点不在复杂度而在把环形、跳过已收、间隔数递增这三个条件同时正确建模——任何一处理解偏差都会导致样例都过不了。5. 粉刷匠逆向思维与百万级数据的降维5.1 正向模拟为什么不可行n 行 m 列k 次操作每次刷一整行或一整列。n、m、k 最大都是 10⁶。如果真去维护一个二维数组10⁶ × 10⁶ 直接爆内存就算只记录操作正向模拟每次刷一行要改 m 个格子总操作量 10⁶ × 10⁶ 10¹²完全不可能。这道题的设计意图非常明确逼你放弃“模拟过程”转而“看结果由谁决定”。5.2 逆向扫描的关键洞察最后一次操作会覆盖它所在行或列的所有格子。倒数第二次操作如果它刷的行/列和最后一次不同那么它覆盖的格子里除了被最后一次交叉覆盖的那个点其余都保留。以此类推从后往前扫每次操作真正“生效”的格子数 该行或列的总格数 − 已经被后续操作覆盖的交叉点数。具体做法记录每一行最后一次被刷的时间戳和颜色每一列同理。然后从后往前遍历操作维护“已经被后续操作占用的行数”和“列数”。对于第 i 次操作刷行 y它新确定的蓝色格子数 m − 已占用的列数×z 1 ? 1 : 0同时把这一行标记为已占用。列操作对称处理。// 核心思路示意从后往前统计每次操作新影响的格子 // row_used / col_used 记录该行/列是否已被更晚的操作覆盖 // 答案累加时只算“新确定”的格子颜色由当前操作决定这个思路把 O(nm) 的网格操作降到了 O(k)因为每次操作只做常数次判断。参数上要注意n 和 m 可以到 10⁶但 k 也是 10⁶所以答案可能很大用long long存结果行号和列号从 1 开始数组要开到 10⁶ 1。5.3 这道题教的事先看数据范围再动手30% 的数据 n, m, k ≤ 1000暴力模拟能拿 30 分另外 30% 数据 n ≤ 10 但 m、k 到 10⁵说明可以枚举行但列要优化100% 数据全拉满必须用逆向思维。这种“分层给分”的设计在竞赛里很常见它的潜台词是不要一上来就追求最优解先拿稳部分分再根据数据范围的特征找突破口。粉刷匠这道题如果读题时先看数据规模表就会立刻意识到正向模拟没戏从而主动往“最后一次操作决定最终颜色”这个方向想——这是血泪经验里最值钱的一条。6. 易漏点与易错点四道题里埋的那些坑6.1 易漏点一距离单位与房号差混淆好朋友题里相邻房子距离 10 米距离 房号差 × 10。很多人写完abs(i - x)就交卷了忘了乘 10。为什么漏因为题目描述里“10 米”出现在很靠前的位置读题时注意力还在“买房”“预算”这些词上单位信息容易被跳过。怎么补养成习惯凡是题目给了物理单位或换算关系读完立刻在草稿纸上写一行“距离 房号差 × 10”编码时对着抄。6.2 易漏点二前缀和减的是 x-1 不是 x统计人口题里区间 [x, y] 的和是pre[y] - pre[x-1]。写成pre[y] - pre[x]的话会把第 x 户漏掉。为什么漏因为直觉上“从 x 开始”就想减pre[x]但前缀和的定义是“前 i 项之和”pre[x]包含了第 x 项要得到从 x 开始的和必须减到 x-1。怎么补记一句口诀“前缀和区间左减一”。或者用 0 下标思维验证如果 x 1pre[0]必须是 0减pre[0]才对减pre[1]就把第一户丢了。6.3 易错点三卫星题的“间隔”是在未接收里数卫星题最大的理解陷阱是“间隔 k 颗”到底怎么数。规则说“接收过的卫星不再接收第二次信号即此卫星不计算在间隔的卫星数量中”这意味着数间隔时只数还没接收的。很多人按物理位置直接跳把已收的也算进去结果样例都过不了。为什么错因为日常语言里“间隔”是按位置数的但题目重新定义了计数规则。怎么补读题时把“不计算在内”这几个字圈出来然后用 n 5 的样例手动走一遍确认自己的理解和样例输出一致再动手写代码。6.4 易错点四粉刷匠的时间戳方向搞反粉刷匠要从后往前扫因为后面的操作覆盖前面的。如果从前往后扫每次操作都会被后续操作部分覆盖没法直接累加。为什么容易反因为人读操作序列习惯从第一条开始。怎么补在草稿上把操作编号标出来画一个箭头从 k 指向 1提醒自己“最后刷的说了算”。另外注意同一行被刷多次时只有最后一次的颜色有效逆向扫描天然处理了这一点正向则要额外记录。6.5 易漏点五输入输出效率与文件格式整份卷子有两道题明确提示用 scanf/printf而且比赛要求按题目英文名建目录、源程序放对应目录下。很多人代码写对了但文件建错位置或者用了 cin 被卡时限白白丢分。为什么漏因为平时练习都在在线评测上点提交不涉及目录结构。怎么补赛前用模拟环境练一次在本机建friend/、people/、star/、paint/四个目录把源程序分别放进去确认路径无误。输入输出上数据量过万就默认用 scanf/printf别赌评测机性能。7. 复习清单从这份卷子倒推的查漏补缺路线把四道题拆完复习重点其实已经浮出来了。下面这张表是按“考点—对应题目—自检标准”整理的可以对着逐项打勾考点对应题目自检标准多条件枚举与边界排除好朋友能一次写对三个 continue 的顺序且距离乘 10 不漏前缀和区间查询统计人口能默写pre[y] - pre[x-1]并解释为什么减 x-1环形模拟与规则理解卫星能用 n5 手动复现样例说清“间隔”的计数范围逆向思维与时间戳粉刷匠能说出为什么从后往前扫并手算样例 2 的答案数据规模与复杂度判断全部看到 n、m、k 上限能立刻判断暴力是否可行输入输出效率统计人口、粉刷匠数据量过万时默认 scanf/printf不依赖 cin 优化复习的时候建议按这个顺序走先限时 150 分钟完整做一遍模拟真实比赛节奏然后对答案把错题按上表归类看是“理解错题意”还是“算法选错”还是“边界写漏”最后针对错得最多的那一类找同类型的题再练三道。最容易忽略的是“读题阶段”的复盘——很多人只复盘代码不复盘自己第一遍读题时漏了什么信息。我的习惯是每次模拟赛后把每道题的题面重新读一遍用红笔标出第一遍没注意到的约束条件比如“Pi 0 表示不可卖”“已接收的不计入间隔”“答案不超过 2³¹−1”。这些细节往往就是 10 分和 100 分的差距。从那以后我每次带人备赛都强制走一遍“先读数据范围表、再读样例解释、最后读问题描述”的倒序读题法因为数据范围告诉你算法上限样例解释告诉你规则细节问题描述反而最容易带着先入为主的误解去读。这份四道题的卷子拿去做一次完整的限时自测再按上面的清单逐项补漏比刷十套零散的题都管用。希望帮到你。本文还有配套的精品资源点击获取
简介这份资源是第18届绍兴市少儿信息学竞赛复赛试题文档面向备战NOIP系列赛事的小学高年级及初中信息学选手与辅导教师用于熟悉复赛题型、检验算法与编程基本功。压缩包内共1个docx文件约32KB完整收录比赛题目说明、输入输出格式、样例与数据范围约定并附有比赛目录结构与提交规范提醒。试题围绕“好朋友”“统计人口”“卫星”“粉刷匠”四道题展开分别涉及数组与循环模拟、区间统计与数据结构、环形序列构造、行列染色计数等知识点可帮助读者按题面还原评测要求练习文件读写、边界处理与复杂度控制。目前已有815人学习下载适合作为赛前模拟训练与知识点查漏补缺的参考材料。1. 四道题就是一张地图小学信息学复赛到底在考什么很多人拿到一份少儿信息学竞赛的复赛真题第一反应是“这不就是四道编程题吗”然后埋头去写代码。但真正把这份卷子从头到尾拆一遍会发现它其实是一张非常清晰的知识地图四道题分别对应四个不同的能力层级从最基础的枚举与条件判断到前缀和优化再到模拟与构造最后是逆向思维加数据规模分析。这四道题放在一起恰好覆盖了小学阶段信息学竞赛的核心考点——数组操作、循环控制、边界处理、时间复杂度的直觉判断以及“读题比写代码更重要”这条血泪经验。这份卷子适合两类人一类是正在系统学习 C 或 Pascal、准备参加区市级竞赛的学生可以用它做一次完整的自测另一类是已经学过基础语法但总在比赛中翻车的选手因为它的四道题几乎把小学组最常见的踩坑点都埋了一遍。150 分钟、四道题、每题 10 个测试点这个配置本身就值得研究——它意味着平均每题只有 37 分钟左右读题、建模、编码、调试全算进去时间分配本身就是一道隐形的题。2. 好朋友枚举与距离计算的第一道门槛2.1 题目在考什么这道题的场景很直白一条直线上有 n 套房房号 1 到 n相邻距离 10 米。小 A 住在 x 号房小 B 想买一套离小 A 最近的房子但有两个约束——不能买小 A 那套且房价不能超过预算 m。价格 Pi 为 0 表示该房不可卖。求小 B 能买到的房子离小 A 家的最近距离。核心逻辑拆开来看就三步第一遍历所有房号第二筛掉不可卖的Pi 0和买不起的Pi m以及小 A 自己那套房号等于 x第三在剩下的房里找离 x 最近的距离按 |房号差| × 10 计算。2.2 关键实现与参数说明用 C 写出来大概是这样#include cstdio #include cstdlib #include climits int main() { int n, x, m; scanf(%d %d %d, n, x, m); int best INT_MAX; // 初始化为无穷大表示还没找到 for (int i 1; i n; i) { int p; scanf(%d, p); if (i x) continue; // 不能买小A自己的房子 if (p 0) continue; // 不可卖 if (p m) continue; // 买不起 int dist abs(i - x) * 10; // 房号差乘以10米 if (dist best) best dist; } printf(%d\n, best); return 0; }这段代码里最容易被忽略的是best的初始值。如果初始化为 0后面比较dist best永远不成立答案就错了。用INT_MAX是稳妥做法但要注意题目保证至少有一套可买的房所以循环结束后best一定被更新过。另一个细节是距离计算题目说相邻房子距离 10 米房号差为 d 时距离是 d × 10不是 d。样例 1 里小 A 住 2 号可买的最近是 4 号房号差 2距离 20验证了这个公式。2.3 复杂度与数据范围的关系n 最大 100O(n) 的遍历完全够用甚至 O(n²) 都不会超时。但这道题的价值不在于复杂度而在于“多条件筛选”的编码习惯三个 continue 的顺序其实有讲究。如果先判断价格再判断房号逻辑上没问题但把i x放在最前面可以少做一次价格读取后的判断——不过这里价格已经读进来了所以顺序不影响正确性只影响可读性。梳理下来会发现这类题最稳的写法是“先排除所有不可能再在可能里找最优”而不是“边找边判断”后者容易在边界上翻车。3. 统计人口前缀和从 O(nm) 到 O(nm) 的跨越3.1 暴力思路为什么不够题目给 n 户人家的人口数m 次询问每次问“编号 x 到 y 的人都不在家能核查到多少人口”。翻译一下就是总和减去区间 [x, y] 的人口和。最直白的做法是每次询问都从 x 加到 y再拿总和去减。n 和 m 最大都是 50000最坏情况下每次询问区间覆盖整个数组总操作次数 50000 × 50000 2.5 × 10⁹1 秒时限下必然超时。这就是这道题埋的第一个坑数据范围里 30% 是 n, m ≤ 10050% 是 n ≤ 1000、m ≤ 10000只有 100% 才拉到 50000。如果只盯着小数据写暴力能拿 50 分但复赛要的是满分。3.2 前缀和的标准解法前缀和的核心就一句话预处理一个数组pre[i]表示前 i 户的总人口那么区间 [x, y] 的和等于pre[y] - pre[x-1]。每次询问 O(1)总复杂度 O(n m)。#include cstdio int a[50005]; long long pre[50005]; // 用long long防止累加溢出 int main() { 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]; // 前缀和递推 } long long total pre[n]; for (int i 0; i m; i) { int x, y; scanf(%d %d, x, y); long long away pre[y] - pre[x - 1]; // 区间和 printf(%lld\n, total - away); } return 0; }几个参数要盯住pre数组用long long因为题目说答案不超过 2³¹−1但前缀和累加过程中可能短暂超过 int 范围虽然这题人口数不大但养成习惯没坏处pre[0]默认为 0这是递推的起点不能漏区间和公式是pre[y] - pre[x-1]减的是x-1不是x这是前缀和最经典的易错点。3.3 输入输出效率的隐性考点题目末尾专门提示“输入输出数据比较多建议用 scanf、printf”。这不是客套话。m 最大 50000如果用 cin/cout 且没关同步在某些评测机上确实可能卡时限。小学组选手往往习惯用 cin这道题就是一次明确的提醒数据量上万的时候输入输出方式要纳入考虑。另外输出格式是每行一个数用printf(%lld\n, ...)比cout ... endl更稳因为 endl 会强制刷新缓冲区频繁调用有开销。4. 卫星环形模拟与构造题的思维转换4.1 题目到底在求什么这道题是四道里最绕的。它给一个 n要求设计一个 1 到 n 的环形排列使得按照特定规则接收信号时接收顺序恰好是 1, 2, 3, …, n。规则是先接收 1 号卫星然后间隔 1 颗跳过 1 颗未接收的接收下一颗再间隔 2 颗接收下一颗间隔数等于上一次接收到的卫星编号。已接收的卫星不再计数。换句话说题目不是让你模拟接收过程而是让你反推排列。这是典型的构造题正向规则已知反向求初始状态。4.2 从样例反推规律看 n 5 的样例输出1 3 2 5 4。验证一下环上顺序是 1→3→2→5→4→1。先收 1 号间隔 1 颗未接收的1 后面是 3已收不3 还没收但 1 刚收完下一个是 3间隔 1 颗意味着跳过 3这里要仔细。实际上规则里的“间隔 1 颗”指的是在未接收的卫星中数 1 颗跳过然后收下一颗。按样例的环 1,3,2,5,4收 1 后未收的是 3,2,5,4间隔 1 颗跳过 3收 2——但 2 在环上的位置是第三个说明“间隔”是在环上按物理顺序数跳过已收的不算。这个细节非常容易读错也是这道题最大的理解门槛。梳理下来构造的规律是第 k 步接收的卫星编号是 k而它在环上的位置需要满足“从上一个接收位置出发在剩余未接收卫星中数 k 颗跳过 k 颗下一颗就是 k1 号”。反推时可以用一个动态数组维护剩余卫星每次按规则插入。4.3 数据规模决定算法选择n 最大 1000050% 是 1000。如果用链表模拟插入O(n²) 在 10000 时是 10⁸ 级别勉强能过但很险更稳的做法是用树状数组或线段树维护“第 k 个未接收位置”把单次查询降到 O(log n)。不过对小学组来说O(n²) 的数组模拟每次线性扫描找第 k 个未收的在 n 10000 时大约 5000 万次操作C 下 1 秒内通常能跑完属于“能过但不优雅”的解法。这道题真正的难点不在复杂度而在把环形、跳过已收、间隔数递增这三个条件同时正确建模——任何一处理解偏差都会导致样例都过不了。5. 粉刷匠逆向思维与百万级数据的降维5.1 正向模拟为什么不可行n 行 m 列k 次操作每次刷一整行或一整列。n、m、k 最大都是 10⁶。如果真去维护一个二维数组10⁶ × 10⁶ 直接爆内存就算只记录操作正向模拟每次刷一行要改 m 个格子总操作量 10⁶ × 10⁶ 10¹²完全不可能。这道题的设计意图非常明确逼你放弃“模拟过程”转而“看结果由谁决定”。5.2 逆向扫描的关键洞察最后一次操作会覆盖它所在行或列的所有格子。倒数第二次操作如果它刷的行/列和最后一次不同那么它覆盖的格子里除了被最后一次交叉覆盖的那个点其余都保留。以此类推从后往前扫每次操作真正“生效”的格子数 该行或列的总格数 − 已经被后续操作覆盖的交叉点数。具体做法记录每一行最后一次被刷的时间戳和颜色每一列同理。然后从后往前遍历操作维护“已经被后续操作占用的行数”和“列数”。对于第 i 次操作刷行 y它新确定的蓝色格子数 m − 已占用的列数×z 1 ? 1 : 0同时把这一行标记为已占用。列操作对称处理。// 核心思路示意从后往前统计每次操作新影响的格子 // row_used / col_used 记录该行/列是否已被更晚的操作覆盖 // 答案累加时只算“新确定”的格子颜色由当前操作决定这个思路把 O(nm) 的网格操作降到了 O(k)因为每次操作只做常数次判断。参数上要注意n 和 m 可以到 10⁶但 k 也是 10⁶所以答案可能很大用long long存结果行号和列号从 1 开始数组要开到 10⁶ 1。5.3 这道题教的事先看数据范围再动手30% 的数据 n, m, k ≤ 1000暴力模拟能拿 30 分另外 30% 数据 n ≤ 10 但 m、k 到 10⁵说明可以枚举行但列要优化100% 数据全拉满必须用逆向思维。这种“分层给分”的设计在竞赛里很常见它的潜台词是不要一上来就追求最优解先拿稳部分分再根据数据范围的特征找突破口。粉刷匠这道题如果读题时先看数据规模表就会立刻意识到正向模拟没戏从而主动往“最后一次操作决定最终颜色”这个方向想——这是血泪经验里最值钱的一条。6. 易漏点与易错点四道题里埋的那些坑6.1 易漏点一距离单位与房号差混淆好朋友题里相邻房子距离 10 米距离 房号差 × 10。很多人写完abs(i - x)就交卷了忘了乘 10。为什么漏因为题目描述里“10 米”出现在很靠前的位置读题时注意力还在“买房”“预算”这些词上单位信息容易被跳过。怎么补养成习惯凡是题目给了物理单位或换算关系读完立刻在草稿纸上写一行“距离 房号差 × 10”编码时对着抄。6.2 易漏点二前缀和减的是 x-1 不是 x统计人口题里区间 [x, y] 的和是pre[y] - pre[x-1]。写成pre[y] - pre[x]的话会把第 x 户漏掉。为什么漏因为直觉上“从 x 开始”就想减pre[x]但前缀和的定义是“前 i 项之和”pre[x]包含了第 x 项要得到从 x 开始的和必须减到 x-1。怎么补记一句口诀“前缀和区间左减一”。或者用 0 下标思维验证如果 x 1pre[0]必须是 0减pre[0]才对减pre[1]就把第一户丢了。6.3 易错点三卫星题的“间隔”是在未接收里数卫星题最大的理解陷阱是“间隔 k 颗”到底怎么数。规则说“接收过的卫星不再接收第二次信号即此卫星不计算在间隔的卫星数量中”这意味着数间隔时只数还没接收的。很多人按物理位置直接跳把已收的也算进去结果样例都过不了。为什么错因为日常语言里“间隔”是按位置数的但题目重新定义了计数规则。怎么补读题时把“不计算在内”这几个字圈出来然后用 n 5 的样例手动走一遍确认自己的理解和样例输出一致再动手写代码。6.4 易错点四粉刷匠的时间戳方向搞反粉刷匠要从后往前扫因为后面的操作覆盖前面的。如果从前往后扫每次操作都会被后续操作部分覆盖没法直接累加。为什么容易反因为人读操作序列习惯从第一条开始。怎么补在草稿上把操作编号标出来画一个箭头从 k 指向 1提醒自己“最后刷的说了算”。另外注意同一行被刷多次时只有最后一次的颜色有效逆向扫描天然处理了这一点正向则要额外记录。6.5 易漏点五输入输出效率与文件格式整份卷子有两道题明确提示用 scanf/printf而且比赛要求按题目英文名建目录、源程序放对应目录下。很多人代码写对了但文件建错位置或者用了 cin 被卡时限白白丢分。为什么漏因为平时练习都在在线评测上点提交不涉及目录结构。怎么补赛前用模拟环境练一次在本机建friend/、people/、star/、paint/四个目录把源程序分别放进去确认路径无误。输入输出上数据量过万就默认用 scanf/printf别赌评测机性能。7. 复习清单从这份卷子倒推的查漏补缺路线把四道题拆完复习重点其实已经浮出来了。下面这张表是按“考点—对应题目—自检标准”整理的可以对着逐项打勾考点对应题目自检标准多条件枚举与边界排除好朋友能一次写对三个 continue 的顺序且距离乘 10 不漏前缀和区间查询统计人口能默写pre[y] - pre[x-1]并解释为什么减 x-1环形模拟与规则理解卫星能用 n5 手动复现样例说清“间隔”的计数范围逆向思维与时间戳粉刷匠能说出为什么从后往前扫并手算样例 2 的答案数据规模与复杂度判断全部看到 n、m、k 上限能立刻判断暴力是否可行输入输出效率统计人口、粉刷匠数据量过万时默认 scanf/printf不依赖 cin 优化复习的时候建议按这个顺序走先限时 150 分钟完整做一遍模拟真实比赛节奏然后对答案把错题按上表归类看是“理解错题意”还是“算法选错”还是“边界写漏”最后针对错得最多的那一类找同类型的题再练三道。最容易忽略的是“读题阶段”的复盘——很多人只复盘代码不复盘自己第一遍读题时漏了什么信息。我的习惯是每次模拟赛后把每道题的题面重新读一遍用红笔标出第一遍没注意到的约束条件比如“Pi 0 表示不可卖”“已接收的不计入间隔”“答案不超过 2³¹−1”。这些细节往往就是 10 分和 100 分的差距。从那以后我每次带人备赛都强制走一遍“先读数据范围表、再读样例解释、最后读问题描述”的倒序读题法因为数据范围告诉你算法上限样例解释告诉你规则细节问题描述反而最容易带着先入为主的误解去读。这份四道题的卷子拿去做一次完整的限时自测再按上面的清单逐项补漏比刷十套零散的题都管用。希望帮到你。本文还有配套的精品资源点击获取
