1. 题目理解与整体思路1.1 题目到底在说什么先不急着贴代码我们把题目翻译成人话。现在会有一张二维的地面虽然没有明确边界但实际数据范围有限我们完全不需要真正开一个二维数组去模拟。题目会依次给出 n 张地毯的信息每张地毯用四个整数 (x, y, a, b) 描述含义是这张地毯的左下角落在 (x, y)向右延伸 a向上延伸 b。换句话说这张地毯覆盖的区域是横向从 x 到 xa纵向从 y 到 yb 的闭区间矩形。最后给一个查询点 (px, py)让你说出这个点被哪张地毯盖住。这里有个关键细节地毯是依次铺上去的后铺的会压住先铺的所以如果一个点同时被多张地毯覆盖要输出编号最大也就是最上面的那一张。很多同学第一次看到这个题会下意识地想到开一个二维数组逐张地毯把覆盖的格子填成编号最后直接读答案。这个思路本身没错但有两个问题第一题目数据范围里坐标可以到 10000如果开一个 10001×10001 的矩阵内存就已经是按亿计的格子Python 里即使每个格子只占一个字节也要一个 G 左右明显不现实第二就算内存扛得住时间复杂度也会随着坐标范围爆炸。所以正确做法是把问题抽象成“判断点是否在矩形内”的几何题每次查询只需要遍历地毯列表做一次常数级别的大小比较即可时间和空间都被压缩到了极致。到这里题目的本质已经很清楚它考察的是对“区间包含”的理解以及枚举顺序的选择而不是真正的数据结构与算法难题。这也是它为什么适合做提高组的第一题门槛低但细节多。1.2 为什么必须倒序枚举这是整道题最核心的思维点。地毯一张张往上铺最晚铺上去的在最上面所以查询点被哪些地毯覆盖时其中编号最大的那张就是最终答案。从编号 n 开始往前逐张检查第一次遇到覆盖该点的地毯就可以立刻输出并结束这就是典型的“逆向思维”。如果正序枚举从第 1 张地毯往后找你找到第一张覆盖点的地毯时并不能确定它是不是最上面的必须把剩下所有地毯都检查完才能知道最终的覆盖结果虽然你也可以在循环中不断更新覆盖该点的最大编号但这样无论如何都要遍历完整张表复杂度同样是 O(n)并没有更差。只是从代码可读性和“找到即返回”的角度来看倒序显然更符合直觉也更省事——一旦找到直接 break 输出不需要维护任何中间状态。从理论角度解释一下如果我们把铺地毯的过程看成一个栈地毯编号就是入栈顺序后入栈的在上方查询点被覆盖意味着它在某个栈区间内而我们要找的答案是栈顶方向第一个满足条件的元素。倒序遍历本质上是维护了一个从栈顶往下的扫描过程第一次命中的元素天然就是答案。这个“倒序思维”在后续很多题目里都会反复出现比如铺砖块、叠箱子、撤销操作模拟等把它理解透绝对值回票价。1.3 复杂度分析与数据结构选型先给结论时间复杂度 O(n)空间复杂度 O(n)。n 的范围在题目中是 10000 级别所以最坏情况下循环一万次Python 完全无压力即使是老旧的评测机也跑得飞快。关于数据结构我的建议是直接用列表存元组。每张地毯用一个四元组 (x, y, a, b) 保存索引从 0 到 n-1 对应编号 1 到 n或者也可以拆成四个平行列表 xs, ys, as, bs用下标访问。两种写法在性能上几乎没有差别元组方案更直观也更符合“一行一对象”的建模方式。还有一种做法是定义一个小类或命名元组但考虑到题目规模很小这样做反而增加了不必要的模板代码属于过度设计。为什么不需要哈希表或者前缀和之类的高级优化因为查询只有一个点不是多个查询不需要预处理查询效率坐标范围虽然大但地毯数量少直接枚举就足够。记住一个原则算法题首先要满足数据范围的约束其次才是追求花哨。对于这个数据量O(n) 的模拟就是最优解任何更复杂的结构都是画蛇添足。2. 核心细节解析与实操要点2.1 输入格式与边界处理这道题的输入格式是第一行一个整数 n接下来 n 行每行四个整数 x, y, a, b最后一行也是两个整数代表查询点坐标。很多初学 Python 刷算法题的同学会用 input() 一行行读这样当然可行但在大规模输入下会比较慢。更稳妥的做法是用 sys.stdin 一次性读取全部内容再按空白字符切分这样既快又不容易因为换行符问题出错。有一点需要特别提醒题目里的 a 和 b 是地毯“向上”和“向右”的长度不是右上角的坐标。也就是说地毯覆盖的横坐标范围是 [x, xa]纵坐标范围是 [y, yb]而不是把 a 和 b 当成右上角的两个坐标。这个理解偏差会导致你莫名少算一块区域或者多算一块区域是初学者最容易出问题的点。我自己第一次写的时候也栽在这里还把x a写成了a - x结果样例都过不去。边界条件方面查询点的坐标可能等于地毯边界也可能小于任何地毯的左下角坐标甚至可能是负数。原题的数据范围保证了非负但逻辑上我们不必依赖这个假设判断区间时统一用大于等于和小于等于即可程序自然能处理负数坐标。关键是闭区间判断只要 px x and px x a and py y and py y b 就认为被覆盖。2.2 判断覆盖条件的数学原理说到底判断“点是否在矩形内”就是一个区间包含问题。二维矩形覆盖可以拆成两个独立的一维区间判断横坐标上 px 落在 [x, xa] 内纵坐标上 py 落在 [y, yb] 内两个条件同时满足点就在矩形内部包括边界。这里我用的是“同时满足”这个逻辑关系在代码里就是 and 连接。为什么可以拆开因为矩形是横平竖直的它是由两个方向的闭区间做笛卡尔积得到的。只要坐标轴平行横向判断和纵向判断互不干扰这是初中几何就应该掌握的性质但在编程里容易由于惯性思维被忽略。很多人会去算点到中心的距离甚至向量叉积其实完全没必要二维矩形包含判断的复杂度就是 O(1)四次数值比较搞定。这里我顺手说一下包含边界的问题。题目文字中经常会用“盖住”这个词并没有特别说明边界算不算。按照惯例和样例推演地毯覆盖的是一个闭区域边界上的点也算被覆盖。如果改成开区间样例都会变。所以代码里必须用 而不是 用 而不是 。这种细节在评测时一旦出错可能你和满分之间就差一个等号。2.3 易错点清单先列一个我自己整理的高频错误对照表方便大家自查易错点错误写法示例正确意识方向搞反正序遍历第一张就输出后铺的在上要取编号最大区间开闭搞错用 或 判断边界边界点也算覆盖用 和 a, b 理解错误把 ab 当成右上角坐标a, b 是相对左下角的延伸长度输出编号错误输出循环下标下标从 0 开始编号是下标加 1无解情况漏处理循环完没有兜底输出无解输出 -1第 4 条尤其值得注意。Python 列表下标从 0 开始而题目要求地毯编号从 1 开始。如果循环变量 i 表示的是列表下标那么命中时应该输出 i 1。很多人在本地测试样例时因为数据恰好是第 0 张地毯覆盖输出 0 和 1 的差别没暴露一提交就 WA。我的建议是先在纸上给地毯标号再对照代码检查一圈确保编号转换没有遗漏。3. 实操过程与完整代码实现3.1 从伪代码到 Python 的步骤拆解写代码之前我习惯先写一遍伪代码把思路固定住。这道题的伪代码很简单读入 n 创建空列表 carpets 循环 n 次 读入 x, y, a, b 把 (x, y, a, b) 加入 carpets 读入 px, py 从 n-1 递减到 0 取 carpets[i] 如果 px 在 [x, xa] 且 py 在 [y, yb] 输出 i1 退出程序 循环结束 输出 -1把伪代码翻译成 Python 时有几个小决策值得说。第一循环用 for i in range(n - 1, -1, -1) 还是 while我倾向 for因为 range 的逆序写法语义清晰也不容易出现死循环唯一要注意的是 range 的步长参数传 -1 时结束值是 -1不包含正好能遍历到下标 0。第二退出程序用 exit() 还是 break 加标志位都可以但如果用 exit()要小心它其实抛出一个 SystemExit 异常在某些在线评测的沙箱环境里可能被拦截为了稳妥我一般用 return把整套逻辑封装进 main 函数里一旦命中直接 return 结束。3.2 完整代码与逐行注释下面是我给出的主推版本兼顾清晰和效率import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) if not data: return n data[0] carpets [] idx 1 for _ in range(n): x, y, a, b data[idx], data[idx 1], data[idx 2], data[idx 3] carpets.append((x, y, a, b)) idx 4 px, py data[idx], data[idx 1] for i in range(n - 1, -1, -1): x, y, a, b carpets[i] if x px x a and y py y b: print(i 1) return print(-1) if __name__ __main__: main()逐行解释一下data 通过 sys.stdin.buffer.read().split() 一次性把标准输入的所有字节读进来再经过 map 转成整数列表这样能保证无论输入怎么排版换行、空格混合都能正确解析。n data[0] 之后用 idx 指针依次取出每组四个参数存成元组。最后两个数才是查询点的坐标注意不要把它误当成地毯坐标去遍历。判断部分用了 Python 支持的多重比较链x px x a它等价于x px and px x a可读性更好也更快。一旦命中就 print(i 1) 并 return避免继续循环。3.3 性能优化与代码变体如果你已经理解了上面的版本我再补充几个变体。第一个变体是拆成平行数组而不是元组列表xs [],ys [],as_ [],bs []每种属性单独存循环时用四个下标访问。这种写法在极大规模数据的题目中能省下创建元组对象的开销但本题目 n 只有一万收益极低可读性反而下降所以我只把写法留在文末不推荐作为首选。第二个提速点是快读。洛谷上 Python 跑这道题直接 input() 也能过但如果以后遇到 n 在百万级别的输入一定要用 sys.stdin.buffer.read()。这里面的原理是 input() 每调用一次都要做一次系统层的读取和编码解析而 read() 只做一次整体读取再把字节流切分成 token省掉了大量重复开销。实测在本地 10 万行输入下快读版本比 input() 版本快出三到五倍属于低投入高回报的技巧。还有一个细节是使用sys.stdout.write(str(res) \n)代替 print。print 在输出一次时区别不大但在频繁输出的题目里差距明显。我一般习惯统一用 sys.stdout.write主要是为了在复杂题目里保持统一的 IO 风格避免一边 print 一边 write 造成的混用习惯。4. 常见问题与排查技巧实录4.1 洛谷评测中的典型错误表现我在实际提交过程中见过三类典型的评测结果对应的原因。第一类是 WA多半是正序遍历输出第一张覆盖地毯这种错误在样例可能就是一张地毯时测不出来第二类是 RE一般是读入数据时下标越界比如查询点坐标被当成地毯参数直接读取了四个数第三类是 TLE在本题几乎不可能出现但如果你用了二维数组模拟一旦坐标范围大的用例就会超时。还有一种 MLE同样源于二维数组这也侧面说明抽象思考的必要性。为了帮大家更直观地定位我整理了一个问题速查表现象可能原因快速排查方法样例输出多个结果循环中多处打印没有及时退出检查命中后是否写 return 或 break输出 0下标当作编号输出检查 print(i 1)输出 -1 但手工验算应该覆盖区间判断用了开区间检查比较符是否为 和 输入读取报错索引越界或空数据打印 data 列表核对长度4.2 边界测试用例设计算法题写完代码最高效的验证手段不是直接交评测而是先自己构造几组边界用例。对于这道题我建议至少准备以下几组第一组是 n1查询点恰好落在地毯边界上比如地毯 (0, 0, 5, 5)查询 (5, 5)应该输出 1第二组是多张地毯覆盖同一区域查询点在最上层地毯内部应该输出最大编号第三组是查询点完全不在地毯上应该输出 -1第四组是地毯 A 覆盖了更广区域地毯 B 缩在其中查询点在 B 内此时应该输出 B 的编号而不是 A 的。下面给一组我本地验证过的完整样例3 0 0 5 5 2 2 3 3 1 1 2 2 3 3分析过程查询点 (3, 3) 被第一张地毯 [0,5]×[0,5] 覆盖也被第二张地毯 [2,5]×[2,5] 覆盖还被第三张地毯 [1,3]×[1,3] 覆盖因为点在第三张的边界上闭区间判断会算它被覆盖。所以正确答案是 3因为编号 3 最上面。这个样例同时考察了边界和倒序遍历。如果你用正序找第一张会输出 1一测就露馅。4.3 实战踩坑记录分享一个我印象深刻的提交经历。当时我用二维差分数组的思维去做先给每张地毯的四个角打标记再用前缀和还原矩阵最后直接取查询点数值。算法本身没有问题但坐标上限是 10000开一个二维列表需要 10001 行、每行 10001 个整数Python 里光是初始化 la [[0] * 10001 for _ in range(10001)]内存就直接爆了Reason 显示 MLE。后来我意识到这道题真正的考点不是二维差分而是你是否能看出“只需要保存地毯对象本身根本不需要模拟地面”。从那以后我养成一个习惯在动手写代码前先估算一下最朴素模拟方案的内存和时间如果超过约束就停下来重新抽象问题而不是硬着头皮优化常数。另一个坑是 print 和输出 -1 的位置。我把输出 -1 放在了循环内部某个分支里导致无解时有多个输出连续 WA 了三发。自那以后我规定自己写“找到即返回”风格的代码时循环外只留一个兜底输出并且保证全代码至多只有一处无解输出。5. 题型延伸与竞赛准备建议5.1 经典变体多组查询与矩形覆盖如果题目改成有 q 组查询点每次都要回答覆盖点的最上地毯编号怎么办这时 O(nq) 的复杂度可能不够。有两个常见优化方向第一种是按地毯编号从大到小把所有查询点离线处理每张地毯更新它覆盖的查询点答案本质上就是把“点查地毯”翻成“地毯找点”第二种是用扫描线思想把地毯的上下边界拆成两条横线维护当前覆盖的区间集合再配合线段树处理但实现复杂度高。大多数情况下n 和 q 都只有 1e4 到 1e5 时离线排序加树状数组是更实用的一条路。如果再加上“矩形可以重叠并且要统计每个查询点被覆盖的层数”那就是经典的矩形覆盖计数问题可以用扫描线加离散化去做。虽然这道题本身不需要这些高级技巧但知道它能通向哪里有助于你把一道入门题纳入自己的知识网络。P1003 看起来简单却正好是这些进阶问题的启蒙题它让你理解矩形覆盖的本质、逆向枚举的意义以及模拟题的边界敏感性。5.2 从这道题看提高组的命题风格作为 NOIP2011 提高组的第一题铺地毯承担的任务是稳定军心它不考冷门算法也不考刁钻边界只考“读题 模拟 逆向思维”。可以说提高组前两题大多都遵循类似逻辑比如后续年份里出现的排队接水、模拟栈等题目难度基准就是“认真分析后二十分钟内能写完”。因此在备赛时千万不要忽视这种基础题它们的价值不是难度而是帮你建立一套标准化的读题和验题流程。建议初学者给每道刷过的题留一个“复盘卡片”记录三件事这道题考察的核心思想是什么我最初的思路哪里偏了如果加大数据范围应该往哪个方向优化。把铺地毯复盘的成果迁移到下一道模拟题上你会发现很多题目之间存在伏笔倒序思维会出现在“弹飞绵羊”一类的题里闭区间判断会出现在几何覆盖题里快读技巧则是所有 Python 选手必备的基础功。5.3 给 Python 选手的备赛小建议不少同学在洛谷刷题时会有一种错觉Python 写算法题不如 C 有优势所以不用太认真。但 P1003 这类题恰恰说明Python 在模拟题上的开发效率远高于 C只要输入输出处理得当性能完全够用。我见过太多人因为担心 TLE一上来就放弃 Python 转 C其实在提高组前几题里Python 的瓶颈往往不是语言本身而是代码里低效的 IO 和多余的数据结构。我的建议是尽早固定一套自己的 IO 模板比如每道题都用 sys.stdin.buffer.read() 加 split 处理输入用 sys.stdout.write 输出把所有逻辑包进 main 函数。这样你刷题时就不需要每次重新考虑细节可以把精力集中在算法思路上。另外善用列表推导式、多重比较链、enumerate 这些 Python 特性能让代码更短也更不容易出错但前提是你完全清楚它们的底层行为而不是为了炫技。结尾写到最后我想分享一点个人体会。这道题我前前后后刷过三遍第一遍用 C 写第二遍用 Python 交第三遍是辅导学弟时重新做了一遍。每次都有新的收获第一次学会了倒序枚举第二次意识到 Python 的快读技巧能救命第三次则是在帮别人调试时发现原来很多人不是不会写判断而是没能在纸上把“地毯覆盖区域”画出来就直接开始敲代码。现在我写题解有个习惯凡是涉及坐标、矩形的题目一定先在草稿纸上画个示意图把闭区间、边界点、覆盖顺序都标出来再动手写。这个习惯帮我避免了一半以上的低级错误。如果你刚接触 P1003建议不要只看题解而是先自己写一版再对照本文调整如果已经 AC也值得试着把代码改写成“平行数组”风格或者模拟多组查询的变体体会不同写法的取舍。算法学习的进步往往就藏在这些微小的重写与反思里。希望这篇题解能帮你少走几步弯路。
