NOIP2011铺地毯信息学竞赛里非常经典的一道送分题。很多过来人可能还记得当年考场上的情景纸面上十几行描述铺地毯、查点、求最上层编号读起来场面不小但只要把题意拆透剩下的就是几十行代码的事。这题适合什么人看刚接触竞赛、想从模拟题入手练手的新手或者做题时总在边界条件上被卡的选手。下面就把题意拆透把两种解法、完整C代码、常见错误全部讲清楚初学的时候如果能看到这种细致拆解多少能少走点弯路。1. 题目背景与核心思路拆解1.1 题目到底在说什么先解决读题问题。地毯不是随便铺的每张地毯给出四个参数左下角坐标(a, b)以及沿 x 轴方向的长度g、沿 y 轴方向的长度k。也就是说这张地毯在地面上覆盖的是一片矩形区域x 的范围是[a, ag]y 的范围是[b, bk]。地毯按照输入顺序依次铺设后铺的会盖住先铺的。最后给一个查询点(x, y)问的是这个点最上层被哪张地毯盖住输出这张地毯的编号从 1 开始如果这个点根本没被任何地毯覆盖输出 -1。注意题目里说得清清楚楚地毯边缘上的点也算被覆盖。这句话是整道题最大的坑后面会专门展开。先把这个基本逻辑记住判断一个点是否在矩形内不是判断“点在格子内”而是判断坐标是否落在闭区间里。很多人看完题的第一反应是要不要开一个二维数组模拟整块地面的状态千万别。地面坐标最大能到十万级别十万乘十万的二维数组在内存和运行时间上都是灾难而且题目只问一个点根本不需要知道整块地面长什么样。模拟整块地面属于典型的“看着题意走不想数据范围”。1.2 数据范围已经帮你选好算法了N 最大只有 10000。这意味着什么哪怕把每张地毯从头到尾扫一遍也只需要一万次判断对计算机来说连零头都算不上。所以这题不需要离散化、不需要扫描线、不需要任何高级数据结构暴力的线性扫描就是标准正解。信息学竞赛里有一个非常重要的意识看到数据范围先判断算法级别。这道题用 O(N) 的复杂度就能过而且 N 本身就很小那么 O(N^2) 其实也可能过只是没必要。恰恰因为有这种宽松的数据范围出题人想考察的就不是“你会不会高级数据结构”而是“你能不能把现实场景准确地翻译成程序逻辑”。很多人在这一步栽跟头不是算法不行是题目没读细。把题目翻译成计算机语言就是给定若干矩形每个矩形有一个编号按编号从小到大依次覆盖求覆盖指定点的最上层矩形的编号。翻译完这道题已经解决一半了。2. 两种解法对比正推与逆序扫描2.1 正推法从第 1 张地毯铺到第 n 张顺着铺地毯的顺序去思考一张一张处理地毯如果当前这第 i 张地毯覆盖了目标点就把答案记录为 i。因为编号越大代表铺得越晚、在地毯堆里越靠上面所以循环结束后存下来的编号自然就是最上层那张地毯的编号。过程可以写成这样int ans -1; for (int i 1; i n; i) { if (a[i] x x a[i] g[i] b[i] y y b[i] k[i]) { ans i; } } cout ans endl;这里的关键点是不要找到第一个覆盖目标点的地毯就break而是要一直更新答案直到循环结束。因为前面的地毯即使盖住了点后面的地毯也可能盖住它最上面的那张永远是编号最大的那一张。这个逻辑不难但考试紧张的时候很容易条件反射地写成“找到就退出”然后就拿了零分。正推法的优势是思考过程符合题目输入的顺序顺着读题就顺下来了。代价是无论答案在第几张代码都得把所有地毯扫一遍才能确定最终答案。当然N 只有一万扫完也无所谓。2.2 逆序法从最上面一层开始往下翻我个人更推荐的做法是从最后一张地毯开始往前查。理由非常朴素既然后铺的盖住先铺的那么最后铺的第 n 张地毯位于最上层。从第 n 张开始往前找第一次发现某张地毯覆盖了目标点它就是要找的答案直接输出就可以结束。可以做个生活化的类比你办公桌上堆了一叠文件有人问你某个位置最上面压着的是哪一页正常人绝不会从最底下开始一张张翻起来而是从最上面开始看第一张盖住目标位置的就是答案。逆序扫描就是把这个日常直觉直接翻译成代码。int ans -1; for (int i n; i 1; i--) { if (a[i] x x a[i] g[i] b[i] y y b[i] k[i]) { ans i; break; } } cout ans endl;逆序法的好处在于它用“从最上面往下找第一张覆盖点”这个过程直接对应了题目要求的“最上层地毯”这个语义。逻辑链条极短写错的可能性远低于正推法。而且如果答案靠后循环能提前结束就算答案靠前最坏也是扫完 n 张复杂度依然是 O(N)。2.3 两种思路怎么选对比维度正推法逆序法核心逻辑从第 1 张扫到第 n 张不断更新答案从第 n 张扫到第 1 张找到第一张即输出循环终止必须扫完所有地毯才能确定答案找到目标即可提前结束代码风险容易误写成“找到第一个就 break”更贴近“最上层”语义不容易写歪复杂度O(N)O(N)最优 O(1)最坏 O(N)考场推荐度可用更推荐在数据范围这么宽松的情况下两种方式都能 AC区别不在性能而在“哪种思路不容易把自己绕进去”。考试求的是稳定逆序法思维负担更小所以我一般建议学生优先写逆序。如果你对正推的“不断更新答案”足够敏感也不会出问题。怕就怕在考场上脑子一热代码一写样例一过结果边界逻辑都没想清楚就交了。3. 完整C代码与关键条件分析3.1 可以直接AC的完整代码下面这份代码是可以直接通过这道题的 C 实现注释也标得很清楚#include iostream using namespace std; const int MAXN 10005; // 分别记录每张地毯左下角坐标 (a[i], b[i]) 以及两个方向长度 int a[MAXN], b[MAXN], g[MAXN], k[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { cin a[i] b[i] g[i] k[i]; } int x, y; cin x y; int ans -1; // 默认没有地毯覆盖 // 逆序查找从最后一张地毯开始往前找 for (int i n; i 1; i--) { if (a[i] x x a[i] g[i] b[i] y y b[i] k[i]) { ans i; break; } } cout ans endl; return 0; }代码量很小核心就是中间那个四条件的判断。但越是这种短代码越容易在小地方翻车。下面把几个决定生死的细节单独拉出来讲。3.2 真正决定对错的三个细节第一个细节为什么条件全部要带等号。题目说了地毯边缘上的点也算被覆盖。那么查询点正好落在左边界x a[i]、右边界x a[i] g[i]、下边界y b[i]、上边界y b[i] k[i]上的时候都必须算作覆盖。如果写成不等的开区间样例大概率能过但评测数据里一定会存在点落在地毯边上的测试点一旦踩中就是整道题丢分。用闭区间是扣题意的写法不是可选项而是必选项。第二个细节g和k是长度不是右上角坐标。有同学直接拿a[i] g[i]当右上角 x 坐标这没错因为左下角加长度确实能得到右边界但有人会把地毯理解成“左上角坐标 右下角坐标”这类输入然后胡乱拼条件。读题时要分清四个参数的含义一个是点两个是长度。这决定了右边界、上边界得自己加出来而不是直接抄一个数。第三个细节编号从 1 开始而数组也建议从 1 开始存。题目说第 1 张地毯编号为 1如果数组从 1 开始存那么直接输出查到的i就是正确的编号。如果从 0 开始存虽然可以在输出时加 1但等于多了一次脑子换算的过程增加了出错机会。竞赛代码里这种小习惯太多了都是在血泪教训中攒下来的。4. 初学者最容易踩的四个坑4.1 差一个等号从满分变零分判断覆盖的核心条件是闭区间还是开区间我见过太多人在这里栽跟头。最典型的问题写法是if (a[i] x x a[i] g[i] b[i] y y b[i] k[i])这写法看着挺像那么回事但它把所有落在边界上的点全部排除了。举个例子一张地毯左下角在(1, 1)长和宽都是 3那么它覆盖的 x 范围应该是 1 到 4y 范围也应该是 1 到 4。查询点(4, 4)正好卡在右上角按题目要求是覆盖的但开区间条件会认为它没被覆盖输出 -1 或者更上层一块根本没盖住它的地毯直接错掉。这种边界题最阴的地方在于你拿样例去测样例可能没有一个点踩在地毯边界上于是本地全过交上去就 WA 几个点。所以以后凡是被“覆盖范围”这类题第一反应就是在每个等号处标记一下边缘算不算题目说了算那就写。4.2 把坐标系当成方格地图这个坑很隐蔽特别是有过二维网格题经验的人容易犯。在做类似“地图上某个格子被覆盖”的题目时格子点的判断往往用x left x right也就是左闭右开区间因为网格的右边界不属于当前格子。但铺地毯里的地面不是格子而是连续的坐标系每个坐标就是一个点。判断一个点是否落在矩形区域内四个边界都是包含的。如果脑子里带着“格子地图”的惯性来写这道题很容易下意识写成左闭右开。建议在草稿纸上画一个坐标系把地毯的四个角标出来再把查询点画上去肉眼看一下边界。这种方式对初学者非常有效能直接把“坐标系点覆盖”和“格子地图覆盖”的区别看清楚。4.3 数组越界和初始化问题题目给的 N 最大是 10000有些同学就非常“精准”地申请int a[10000]。但是循环从 1 到 n当 n 等于 10000 时最后一次访问的是a[10000]而数组下标范围只有 0 到 9999越界了。这种错误在不经意间就会发生。竞赛里处理数组大小有一个通用习惯按数据范围最大值再多开几个比如 10000 的数据就开 10005。反正多几个 int 只占几十字节内存不心疼。不要在这种地方抠门。另外ans 一定要初始化成 -1。如果有同学初始化成 0然后某组数据确实没有任何地毯覆盖输出就成了 0 而不是 -1又是一个白给的 WA。4.4 正推时把编号覆盖关系弄反如果坚持用正推最容易看到这个 bug第一次发现目标点被某张地毯覆盖立刻cout i然后 return。前文说过这种做法只适用于“查询点被第一张碰巧覆盖的地毯就是答案”的假设但题目明确说地毯按顺序铺、后铺的在上所以答案是所有覆盖该点的地毯中编号最大的那张而不是编号最小的那张。一个比较稳的改法是把正推改写成“用 ans 记录当前找到的最大编号”循环结束后输出 ans。也可以把存地毯的数组倒过来从第 n 张开始查本质上就是逆序思路。每次考试后复盘看到这类错误我一般不会简单地说是“粗心”而是建议选手把题目的语义再翻译一遍最上层 最后覆盖 编号最大。只要这几个词在脑子里对齐了代码很难写错。5. 考场上的做题节奏与训练价值5.1 第一题的正确打开方式像这种放在整场考试第一题的题目价值往往不只是 AC 本身还在于帮你稳住考试节奏。拿到题先别急着开写花一两分钟在草稿纸上把样例用手模拟一遍。这个习惯能逼你确认自己真的读懂了题地毯是从哪个坐标开始铺、向哪个方向延伸、边缘点算不算覆盖、输出的是编号还是别的什么。再一个容易被忽略的细节是题目给的参数比较多a、b、g、k四个字母很容易搞混。建议在草稿纸上把每个字母的含义写下来或者在变量命名上直接使用意义更明确的词比如xLeft、yBottom、width、height。考场上时间紧张但读题多花二十秒能省下后面调 bug 的半小时。5.2 从“读题到代码”的翻译训练很多人觉得这题太简单AC 完就觉得没有价值。实际上它是很好的“自然语言转条件表达式”训练。题目描述里的“边缘也算覆盖”翻译成代码就是在判断条件里加等号描述里的“最上层”翻译成代码就是逆序查找或者取最大编号描述里的“第 i 张地毯编号是 i”翻译成代码就是数组下标从 1 开始用。这三重翻译每一重都是一名竞赛选手必须具备的基本功。如果遇到这道题时你觉得自己没问题恭喜你基础功已经比较扎实了如果你看到这题第一反应是想用二维线段树那我反而要劝你先回去练练数据范围敏感度。暴力的地方大胆暴力简单的地方老老实实模拟是竞赛场上非常重要的策略。6. 从这道题延伸出去的三个进阶思考6.1 如果查询不止一个点怎么办原题只查询一个点所以逆序扫描一遍就结束了。如果题目扩展成 m 个查询点朴素做法是每个点都从最后往前扫一遍复杂度是 O(N*M)。当 N 和 M 都到一万左右时运算次数上亿C 勉强能跑但已经很悬了如果 N 和 M 都上十万甚至百万那就必须换方案。更高效的做法是离线扫描线把所有查询点和地毯的左右边界一起按 x 排序用线段树维护 y 方向的覆盖状态。每遇到一块地毯的左边界就在它对应的 y 区间上做一次“赋值式更新”把这段区间的最上层地毯编号整体改成当前编号等扫到查询点时直接单点查询这个 y 坐标对应的编号就是答案。这个做法需要线段树的区间懒标记不是这题本身的要求但作为进阶方向是很好的延伸。6.2 如果 N 变得非常大假设 N 变成了十万或者百万级别而查询仍然只有一个点逆序扫描最坏情况下还是要看这么多地毯但每次判断都是几次整数比较现代评测机跑百万次循环也就是几毫秒的事完全没有压力。真正需要担心的是多次查询乘上大量地毯导致总运算量爆炸。这个例子想说明的道理其实很简单不是所有题目都需要高级数据结构。决定用哪种算法的第一依据一定是数据范围而不是“感觉这题应该考线段树”。如果 O(N) 能过就别给自己加戏。很多选手栽在不该优化的时候强行优化反而把简单题写复杂然后在一个低级细节上出错得不偿失。6.3 这道题带来的三个通用思维第一个是“从后往前”思维。凡是题目里出现“最上面”“最后覆盖”“最新状态”这类关键字可以先想想能不能从后往前处理。这种逆向思维在很多题里都有用比如括号序列、版本覆盖问题、最近一次操作查询本质上都有相似的切入点。第二个是“点在矩形内”的判断模板x0 x x x1 y0 y y y1。这个模板不只在铺地毯里用得到几乎所有几何模拟、碰撞检测、覆盖类问题都会用到。把模板记牢以后遇到类似问题可以少动很多脑子。第三个是“边界条件先行”的习惯。拿到覆盖类题目先问自己边缘算不算区间是闭还是开坐标是连续点还是离散格子这三个问题想清楚了远比急着写主逻辑重要。铺地毯这道题如果我在教学中只能给学生留一句话那就是读题时多画两个坐标轴边界想清楚再敲代码。最后说点个人体会。铺地毯这类题我前前后后陪不少刚接触竞赛的朋友练过发现一个规律能一次 AC 的人往往不是代码敲得最快的而是读题读得最细的。那些把边界等号漏掉的、把长度当坐标用的、把正推写成遇答即走的不是不会写代码而是没把题目语言逐字嚼碎。如果你能把每道送分题都做到不丢分竞赛的下限就已经超过大多数人了。下次再遇到这种题目试着逆序扫一遍顺手把四个边界样例都测一遍省下来的调试时间足够再斟酌一下后面的题目。