企业官网建设流程全解析

1. 题目理解与整体思路

1.1 题目到底在说什么

先不急着贴代码，我们把题目翻译成人话。现在会有一张二维的地面，虽然没有明确边界，但实际数据范围有限，我们完全不需要真正开一个二维数组去模拟。题目会依次给出 n 张地毯的信息，每张地毯用四个整数 (x, y, a, b) 描述，含义是这张地毯的左下角落在 (x, y)，向右延伸 a，向上延伸 b。换句话说，这张地毯覆盖的区域是横向从 x 到 x+a，纵向从 y 到 y+b 的闭区间矩形。最后给一个查询点 (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, x+a]，纵坐标范围是 [y, y+b]，而不是把 a 和 b 当成右上角的两个坐标。这个理解偏差会导致你莫名少算一块区域或者多算一块区域，是初学者最容易出问题的点。我自己第一次写的时候也栽在这里，还把x + a写成了a - x，结果样例都过不去。

边界条件方面，查询点的坐标可能等于地毯边界，也可能小于任何地毯的左下角坐标，甚至可能是负数。原题的数据范围保证了非负，但逻辑上我们不必依赖这个假设，判断区间时统一用大于等于和小于等于即可，程序自然能处理负数坐标。关键是闭区间判断：只要 px >= x and px <= x + a and py >= y and py <= y + b 就认为被覆盖。

2.2 判断覆盖条件的数学原理

说到底，判断“点是否在矩形内”就是一个区间包含问题。二维矩形覆盖可以拆成两个独立的一维区间判断：横坐标上 px 落在 [x, x+a] 内，纵坐标上 py 落在 [y, y+b] 内，两个条件同时满足，点就在矩形内部（包括边界）。这里我用的是“同时满足”这个逻辑关系，在代码里就是 and 连接。

为什么可以拆开？因为矩形是横平竖直的，它是由两个方向的闭区间做笛卡尔积得到的。只要坐标轴平行，横向判断和纵向判断互不干扰，这是初中几何就应该掌握的性质，但在编程里容易由于惯性思维被忽略。很多人会去算点到中心的距离甚至向量叉积，其实完全没必要，二维矩形包含判断的复杂度就是 O(1)，四次数值比较搞定。

这里我顺手说一下包含边界的问题。题目文字中经常会用“盖住”这个词，并没有特别说明边界算不算。按照惯例和样例推演，地毯覆盖的是一个闭区域，边界上的点也算被覆盖。如果改成开区间，样例都会变。所以代码里必须用 <= 而不是 <，用 >= 而不是 >。这种细节在评测时一旦出错，可能你和满分之间就差一个等号。

2.3 易错点清单

先列一个我自己整理的高频错误对照表，方便大家自查：

第 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, x+a] 且 py 在 [y, y+b]： 输出 i+1 退出程序 循环结束 输出 -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，同样源于二维数组，这也侧面说明抽象思考的必要性。

为了帮大家更直观地定位，我整理了一个问题速查表：

4.2 边界测试用例设计

算法题写完代码，最高效的验证手段不是直接交评测，而是先自己构造几组边界用例。对于这道题，我建议至少准备以下几组：第一组是 n=1，查询点恰好落在地毯边界上，比如地毯 (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，也值得试着把代码改写成“平行数组”风格，或者模拟多组查询的变体，体会不同写法的取舍。算法学习的进步，往往就藏在这些微小的重写与反思里。希望这篇题解能帮你少走几步弯路。