2011年NOIP提高组的赛场上很多选手在做第一题时就卡住了。不是卡在算法不会写而是卡在一个看起来很蠢的问题上——铺地毯到底要不要真的“铺”我是后来在刷洛谷的时候碰到这道P1003的看完题面第一反应是这还不简单直接开个二维数组把地毯一层层铺上去不就完了然后我扫了一眼数据范围整个人清醒了。这道题是NOIP2011提高组的第一题理论上属于“保底送分题”但它用最朴素的题目描述藏了一个非常经典的思维陷阱。你要是真去铺地毯时间和空间全炸你要是换个角度想代码写了不到二十行就能过。这篇文章我尽量把完整的推导过程、代码实现、边界条件和踩坑经验都写出来适合刚接触洛谷、准备NOIP或CSP-S的选手也适合那些已经AC但想回头深挖“当时为什么没想出来”的朋友。1. 题目还原NOIP2011提高组的这道“送分题”到底在考什么1.1 完整题目描述先原原本本把题面摆出来方便没做过的人直接看。为了准备一个独特的颁奖典礼组织者在会场的一片矩形区域可看做是平面直角坐标系的第一象限铺上一些矩形地毯。一共有 n 张地毯编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意该点被地毯覆盖当且仅当该点在矩形地毯的边界上或内部。输入格式第一行一个整数 n表示总共有 n 张地毯。接下来的 n 行中第 i1 行表示编号 i 的地毯的信息包含四个整数 a、b、g、k每两个整数之间用一个空格隔开分别表示铺设地毯的左下角的坐标 (a, b) 以及地毯在 x 轴和 y 轴方向的长度。第 n2 行包含两个整数 x 和 y表示所求的地面的点的坐标。输出格式输出 1 个整数表示所求的地毯的编号若此处没有被地毯覆盖则输出 -1。样例输入3 1 0 2 3 0 2 3 3 2 1 3 3 2 2样例输出31.2 从题面里挖出三个关键信号很多时候题目不是读不懂是读太快把关键信息漏了。这道题里有三处词句值得圈出来第一“后铺的地毯覆盖在前面已经铺好的地毯之上”。这句话直接决定了答案的优先级覆盖同一个点的多张地毯里编号最大的那张一定在顶上。换句话说地毯的编号顺序就是“层级顺序”越往后编号越靠上。第二“该点在矩形地毯的边界上或内部”。这句话说明矩形边框上的点同样算被覆盖。很多错误提交就栽在这里判断条件用了而不是直接把边界丢掉。题目说得明明白白但越简单的条件越容易在写代码时忽略。第三“最上面的那张地毯”。题目只关心一个点只关心最上面那张地毯完全不关心这个点下面压了几张、分别是谁。这个“只问一单点 只问最顶层”的特征是后续所有优化思路的根源。1.3 难在哪难在“看穿它不需要模拟”说句公道话这道题的代码难度几乎为零小学数学就能判断一个点是否在矩形里。它真正的难度在阅读题面后的第一反应——你被“铺地毯”这个动词带跑了。铺地毯是一个过程有先后顺序有覆盖动作有最终状态。正常人都会想那我就照着这个顺序一层层铺上去最后看看指定点上是哪张。问题是题目给的坐标范围根本不允许你真的去“铺”每一块区域。如果你在比赛时读完题就动手写一个二维数组模拟恭喜你你已经掉进出题人挖好的坑里了。接下来要么想尽办法优化但依然超时要么换个数据结构强行维护白白消耗大量时间。这道题虽然只是提高组第一题但它考察的是竞赛里最根本的一项能力动手写代码之前先抬头看数据范围。2. 模拟陷阱为什么铺地毯不能真的“铺”2.1 直接模拟的复杂度到底有多离谱先做一道简单的算术题。题目中 n 的范围是 n ≤ 10000坐标取值范围为 a、b、g、k 都可以达到 100000。如果采用最粗暴的做法构造一个足够大的二维数组来表示会场地面然后每输入一张地毯就两层循环把该地毯覆盖的所有格子都标记成当前地毯编号那么结果如下空间复杂度坐标范围最大是 100000 × 100000 10^10。开一个整型二维数组哪怕每个格子只用 4 字节也需要 4 × 10^10 字节也就是 40GB。这显然不可能。用 Python 的 list 嵌套存更是直接内存爆炸。时间复杂度每张地毯最坏可以覆盖 100000 × 100000 10^10 个格子n 10000 张地毯总操作量就是 10^14 的量级。就算每秒钟能执行 10^9 次简单操作也需要 10^5 秒超过一天。所以直接模拟在数据最强的情况下无论是时间还是空间都属于“绝对不可能通过”的方案。方案时间复杂度空间复杂度能否通过二维数组模拟O(n × 10^10)O(10^10)完全不可行把地毯拆成区间逐行维护O(n × k × logN) 级别取决于实现勉强但代码量爆炸逆向遍历判断单点O(n)O(n)轻松通过我还见过一种“改进模拟”不建二维数组而是把每张地毯拆成一行一行的区间然后用线段树或者差分数组维护每一行。这种做法的复杂度大约是 O(n × K × logN) 级别K 取决于地毯的纵向长度。在 n 10000、坐标范围 100000 时依然非常吃力而且代码量非常大。本来十行就能过的题何必呢。2.2 问题真正的突破口查询是单点的这道题和普通模拟题最大的区别在于它只问一个点的覆盖情况而不是整片区域的覆盖情况。如果一个题目要求你回答“整片区域上每个位置最上层的地毯编号”那你确实需要处理所有格子模拟或者区间操作都绕不开。但这题只问 (x, y) 这一个点。也就是说根本不需要知道其他格子是什么状态。既然只需要判断一个点就完全没有必要把整个地图构建出来。打个比方你要知道某个位置被哪一层油漆覆盖最直接的办法不是把几十层油漆全部重新刷一遍看结果而是从最上面一层开始一层一层往下看看哪一层覆盖了这个位置。一旦找到了底下是什么颜色根本不重要。这个“只看目标点”的思路是很多模拟题的通用逃生通道。每次拿到一个模拟题先问问自己题目要我输出的最终结果是不是只需要局部信息如果是那大概率存在不需要全量模拟的解法。2.3 一个关键结论只要能回答“点 (x, y) 是否在某张地毯范围内”并且能决定从哪张地毯开始判断问题就解决了。地毯每次铺设都会覆盖之前的区域因此覆盖某个点的所有地毯中编号最大的那张就是最终可见的那张。所以判断顺序应该是“从编号 n 到编号 1”也就是从后往前遍历。遍历到第一个满足“点在地毯内”的地毯直接输出它的编号。至此整道题的核心解法已经浮出水面解题过程不需要建立任何二维结构只需要一个长度为 n 的数组来存储地毯信息即可。3. 核心解法从后往前找最上层地毯的逆向思维与Python代码3.1 逆向思维的核心逻辑正向思维是我铺我铺我铺最后看这个点上面是谁。逆向思维是我从最上面一层往下数第一个盖住这个点的就是答案。两种思维的差别体现在复杂度上正向模拟需要处理所有地毯覆盖过的所有格子复杂度极高。逆向判断每次只需要 O(1) 时间判断一个点是否在矩形内总共 n 次复杂度 O(n)。n 最大 10000O(n) 的复杂度在 Python 里非常轻松哪怕不用任何读入优化也能通过。要判断点 (x, y) 是否在第 i 张地毯内先把第 i 张地毯的信息转换为“左下角坐标 右上角坐标”。已知左下角为 (a, b)x 方向长度为 gy 方向长度为 k那么右上角就是 (a g, b k)。于是判断条件为a x a g 且 b y b k注意等式两端的等号因为边界算作覆盖。第 4 章我会专门展开讲这一点。3.2 完整代码与逐段讲解下面是这道题在 Python 里最简洁也最经典的写法def main(): n int(input()) carpets [] for _ in range(n): a, b, g, k map(int, input().split()) carpets.append((a, b, a g, b k)) # 直接存左下角和右上角 x, y map(int, input().split()) for i in range(n - 1, -1, -1): # 从最后一张地毯往前找 left, bottom, right, top carpets[i] if left x right and bottom y top: print(i 1) # 地毯编号从 1 开始 return print(-1) # 没有地毯覆盖该点 if __name__ __main__: main()逐段解释n int(input())读取第一行的整数表示地毯数量。循环 n 次读入每张地毯的四个整数 a、b、g、k。注意这里直接计算了a g和b k把它们作为右上角坐标存入元组。这样后续判断时不需要重复计算。x, y map(int, input().split())读入查询点的坐标。range(n - 1, -1, -1)是从 n-1 到 0 的倒序遍历。因为列表下标从 0 开始而地毯编号从 1 开始所以下标 i 的地毯在编号上对应 i1。元组解包left, bottom, right, top carpets[i]分别取出左下角 x、左下角 y、右上角 x、右上角 y。判断点是否在矩形内满足就打印i 1并直接退出函数。如果循环结束都没有找到说明该点没有被任何地毯覆盖输出 -1。这里有一个容易混的点range(n - 1, -1, -1)中第二个参数-1是循环的终止值循环会取到 n-1, n-2, ..., 0但不会取到 -1。这种写法在竞赛里非常常见写多了会形成肌肉记忆但第一次写的时候建议多确认一遍别写成range(n - 1, 0, -1)那会漏掉下标 0也就是第一张地毯。3.3 读入优化让 Python 在 OJ 上更稳妥虽然 n ≤ 10000 时input()的读入速度已经足够通过但我在实际刷题中见过不少选手在数据量稍大的题目上被 Python 的 I/O 拖垮。P1003 用input()完全没问题但保险起见还是推荐掌握sys.stdin的读取方式。import sys def main(): data list(map(int, sys.stdin.read().split())) n data[0] carpets [] idx 1 for _ in range(n): a, b, g, k data[idx], data[idx 1], data[idx 2], data[idx 3] idx 4 carpets.append((a, b, a g, b k)) x, y data[idx], data[idx 1] ans -1 for i in range(n - 1, -1, -1): l, d, r, u carpets[i] if l x r and d y u: ans i 1 break print(ans) if __name__ __main__: main()这种写法的思路是一次性把整个输入文件读进来按空白字符拆分成整数列表。它的好处是读入次数从 O(n) 次减少到 1 次在数据量大时提升非常明显。代码虽然长一点但逻辑依然清晰。后续用idx顺序取数据不需要额外维护复杂的解析状态。很多参加算法竞赛的 Python 选手都知道sys.stdin.read().split()是标配读入方式。它在处理多组测试数据时尤其方便。P1003 虽然用不上但养成这个习惯遇到 n 达到几十万的题目时会从容很多。3.4 为什么存储结构选择元组列表这里还有一个选型问题carpets用列表存元组还是用 4 个独立列表从功能上看两种都能实现。但从代码可读性上说列表存元组更符合“一张地毯就是一条完整记录”的直觉。从执行效率上看Python 的元组访问和列表访问差别不大4 个独立列表的访问方式可能稍微快一点但这道题 n 只有 10000差别可以忽略。所以我在题解里选择了可读性更好的元组列表写法。把左下角坐标和右上角坐标一起存下来在后续判断时直接解包代码一眼就能看懂。竞赛题除了追求 AC也追求在紧张的比赛中快速写出不容易出错的代码可读性本身就是一种抗错能力。4. 边界条件、常见错误与调试实录4.1 最容易翻车的边界条件先说一个我在多个代码交流群里反复看到的错误把边界判断写成a x a g或b y b k。题目原文说得很清楚“该点被地毯覆盖当且仅当该点在矩形地毯的边界上或内部。”所以 (a g, b k) 这个右上角边界本身算覆盖四条边上的点也算覆盖。判断条件必须写成a x a g 且 b y b k如果去掉等号恰好落在边界上的点在你的程序里会被判定为“未覆盖”答案就会和标准输出不一致。这类边界错误在竞赛中非常隐蔽因为样例数据通常不会正好落在边界上本地测样例通过了提交上去却 Wrong Answer而且很难排查。第二个容易翻车的点是最后输出 -1。如果查询点没有被任何地毯覆盖需要输出 -1。很多人会忘记这个分支觉得“既然铺了这么多地毯题目点肯定在某张地毯上”但题目并没有保证这一点。这也是为什么我在第二份代码里用一个ans变量记录答案初始化为 -1找到满足条件的地毯就更新它并跳出循环最后统一输出ans。这种做法比“找到就 print 然后直接 return”多写一行代码但在出题人故意挖坑的题目里会更稳妥。第三个值得注意的地方是地毯编号从 1 开始而 Python 列表下标从 0 开始。在遍历的时候carpets[i]对应的是编号为 i1 的地毯。一旦弄混输出就会整体偏一位。我习惯在变量命名上明确区分carpets[i]存的是编号 i1 的地毯那么输出时一定写i 1而不是i。4.2 本地自测和提交时踩过的坑拿到题目后我一般会先根据样例输入做一次手算验证然后才跑代码。这里把样例的验算过程整理出来帮助新手建立“手动验证”的感觉。样例中有 3 张地毯第 1 张地毯左下角 (1, 0)x 方向长 2y 方向长 3。覆盖区域为 x ∈ [1, 3]y ∈ [0, 3]。第 2 张地毯左下角 (0, 2)x 方向长 3y 方向长 3。覆盖区域为 x ∈ [0, 3]y ∈ [2, 5]。第 3 张地毯左下角 (2, 1)x 方向长 3y 方向长 3。覆盖区域为 x ∈ [2, 5]y ∈ [1, 4]。查询点 (2, 2) 从第 3 张地毯开始判断2 ∈ [2, 5] 且 2 ∈ [1, 4]成立。输出 3。和题目给的样例输出一致。这里不需要再往前看了因为从后往前遍历时第 3 张就是第一张满足条件的地毯也是最上面的那一张。我再补一个自测用例用来检查 -1 分支1 0 0 1 1 5 5判断点 (5, 5) 不在 [0, 1] × [0, 1] 内所以应该输出 -1。这个用例专门用来检查有没有忘记写“没有覆盖”分支。还有一个用来验证边界包含的用例1 0 0 1 1 1 1点 (1, 1) 正好落在地毯右上角按题意应该被覆盖正确输出 1。如果代码里用了类似x a g的判断这个用例会直接暴露问题。我自己在调试时至少遇到过一次这种边界错误而且当时本地跑样例完全没问题直到加了“边界点”这个用例才发现循环条件写错了。4.3 关于 Python 版本的注意点如果你是在洛谷或者其他 OJ 上提交现在一般默认 Python 3。但如果你本地跑的是某些旧教程里的 Python 2 风格代码比如print ans或者raw_input()提交时就会语法错误。我们这里统一使用 Python 3 的语法也就是print(ans)和input()。在洛谷上选择 Python 3 提交即可。另外在 Python 3 中map(int, input().split())返回的是 map 对象它本质上是一个可迭代的迭代器。直接把它赋值给 4 个变量是没问题的因为 Python 会执行迭代解包。但如果把它直接存起来反复使用建议转成 list否则迭代器只能被消耗一次。这个细节在其他题目里有时候会踩坑。还有一个小经验当一行数据很长时input()会读入整行split()会生成一个字符串列表map(int, ...)逐个转 int。整个过程对内存和时间的消耗都不大在 P1003 的数据范围内完全不用担心。所以我认为这道题里读入优化更多是培养习惯而不是硬性需求。5. 延伸从铺地毯到一类“反模拟”题目的通解思路5.1 这类题的共同特征与思维模型做完 P1003我最大的体会是它不只是考一个点是否在矩形内而是在教你一种“反模拟”的思维方式。什么样的问题适合“反模拟”或者说“逆向处理”我总结出几个特征题目描述了一个按时间顺序执行的操作序列比如铺地毯、染色、覆盖、标记。最后要回答的是某一时刻或某个特定目标的状态而不是整个系统的完整状态。操作序列数量较多或者单次操作的影响范围较大导致正向模拟代价过高。后执行的操作在状态上对前一次操作有“覆盖”关系。这类题目几乎都可以考虑“从后往前处理”从最后一次操作开始检查它是否决定了目标点的最终状态。如果是就得到答案如果不是继续往前找。类似题目我再举两个例子洛谷 P1047 校门外的树马路两侧种了一些树然后有若干次操作把某个区间内的树移走。最后问剩下的树有多少棵。这道题既可以用差分数组正着做也可以从后往前判断每个位置最后是否被移走。两种做法都行但出发点完全不同从后往前的思路更接近 P1003。多重涂色问题有一面墙初始是白色每次在某个矩形区域涂上一种颜色后涂的颜色覆盖先涂的。最后问某个小区域是什么颜色。这和 P1003 的模型几乎一样解法也是从后往前找第一个覆盖该区域的涂色操作。我以前做这种题经常陷入一个误区总觉得“按顺序执行的操作就必须按顺序模拟”否则心里不踏实。但实际上算法竞赛考察的是如何高效地得到答案而不是如何忠实地复现过程。当你发现“过程”太庞大而“答案”只需要很少的信息时就该停下来想想能不能跳过过程。5.2 复杂度总结与进阶方向用最终解法解决 P1003时间复杂度是 O(n)空间复杂度是 O(n)。这个复杂度在 n ≤ 10000 时非常轻松在 Python 中几乎可以忽略运行时间。如果 n 扩大到 10^6 呢O(n) 还是能跑但要注意读入速度和存储方式这时用sys.stdin.read().split()和紧凑的数组结构会更有优势。如果题目改成有 m 个查询点问每个点最上层的地毯编号呢对每个点执行一次 O(n) 的检查总复杂度为 O(nm)。在 n 和 m 都是 10^4 量级时10^8 次操作在 Python 里会比较吃力。这时可以换个思路把每个查询点看成一个“点事件”把每张地毯看成一个“矩形区域”先读入所有点和所有地毯再离线处理。例如可以按照地毯编号从大到小把落在当前地毯范围内的点都标记为当前地毯编号这样每个点只会被标记一次。这类做法通常需要配合排序或某种空间索引来优化。不过对于 P1003 本身的单点查询这些都不需要。另外如果你学有余力可以把这道题和“矩形面积并”“矩形覆盖”等经典几何问题放在一起看。P1003 是最简单的矩形包含点判断线段树和扫描线解决的是更复杂的矩形求交、求并问题。从“单点判断”到“区域统计”复杂度会发生变化但背后的几何直觉是相通的。5.3 一点个人体会我在写这份题解时特意把读入优化和边界条件这两个看起来不相关的话题放在一起是因为它们是我在实际提交中踩过最多坑的地方。很多新手把注意力全放在“算法对不对”上却忽略了“输入能不能撑住”和“等号有没有写对”这些细节。P1003 恰好同时包含了这两类陷阱题目描述里藏着思维陷阱边界判断里藏着逻辑陷阱。如果你正在准备算法竞赛或者刚开始刷洛谷我的建议是每做完一道题不要只看 AC 了没有而是回头想一想——如果我是出题人我会在哪里挖坑这道题有没有一种和我最初想法完全不同的解法时间长了你会发现自己对题目的敏感度会明显提升。最后在本地调试时多造几个边界用例不要只拿样例测一下就算完。我个人的习惯是必测的三个用例分别是“恰好在地毯边界上”“完全没有覆盖”“多张地毯覆盖同一点”分别验证边界、-1 输出和“取最上层”这三个关键逻辑。三道都过了这道题才算真正拿稳了。