【NOIP】2011真题解析 luogu-P1003 铺地毯 | GESP三、四级以上可练习
NOIP 2011 提高组真题，枚举与模拟考点应用，重点理解逆向思维（倒序遍历）的优化策略。GESP 三、四级及以上考生可以练习。题目难度⭐⭐★☆☆，洛谷难度等级普及−。
luogu-P1003 [NOIP 2011 提高组] 铺地毯
题目要求
题目描述
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 $n$ 张地毯，编号从 $1$ 到 $n$。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入格式
输入共 $n + 2$ 行。
第一行，一个整数 $n$，表示总共有 $n$ 张地毯。
接下来的 $n$ 行中，第 $i+1$ 行表示编号 $i$ 的地毯的信息，包含四个整数 $a ,b ,g ,k$，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 $(a, b)$ 以及地毯在 $x$ 轴和 $y$ 轴方向的长度。
第 $n + 2$ 行包含两个整数 $x$ 和 $y$，表示所求的地面的点的坐标 $(x, y)$。
输出格式
输出共 $1$ 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出
-1。
输入输出样例 #1
输入 #1
1
2
3
4
5
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
输出 #1
1
3
输入输出样例 #2
输入 #2
1
2
3
4
5
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
输出 #2
1
-1
说明/提示
【样例解释 1】
如下图，$1$ 号地毯用实线表示，$2$ 号地毯用虚线表示，$3$ 号用双实线表示，覆盖点 $(2,2)$ 的最上面一张地毯是 $3$ 号地毯。
【数据范围】
对于 $30\%$ 的数据，有 $n \le 2$。
对于 $50\%$ 的数据，$0 \le a, b, g, k \le 100$。
对于 $100\%$ 的数据，有 $0 \le n \le 10^4$, $0 \le a, b, g, k \le {10}^5$。
noip2011 提高组 day1 第 $1$ 题。
题目分析
这道题的核心考点是模拟和枚举。题目要求找出覆盖目标点 $(x, y)$ 的“最上面”那张地毯。因为地毯是按编号从小到大顺序依次铺设的，后铺的地毯会覆盖在先铺的地毯之上，所以最上面的地毯也就是最后铺设且覆盖了该点的地毯。
1. 数学模型（点在矩形内的判断）
地毯 $i$ 的左下角坐标为 $(a_i, b_i)$，在 $x$ 轴和 $y$ 轴方向的长度分别为 $g_i$ 和 $k_i$。因此，它覆盖的矩形区域是一个横坐标从 $a_i$ 到 $a_i + g_i$，纵坐标从 $b_i$ 到 $b_i + k_i$ 的范围。 判断给定点 $(x, y)$ 是否在这张地毯上的条件为（包含边界）： \(a_i \le x \le a_i + g_i \quad \text{且} \quad b_i \le y \le b_i + k_i\) 只要满足这个条件，点 $(x, y)$ 就被编号为 $i$ 的地毯覆盖。
2. 解题策略（逆向思维优化）
最直观的想法是“正向模拟”：开一个巨大的二维数组代表地板，每拿到一张地毯，就把地毯覆盖区域的格子都填上该地毯的编号（即所谓的“刷表法”）。最后查询 $(x, y)$ 格子里的编号。但题目数据范围中坐标高达 $10^5$，如果定义二维数组会需要 $10^{10}$ 个元素，这会导致严重超内存（MLE）和严重超时（TLE）！
正确的解题思路无需真的去“铺”地毯，只需要记录下每张地毯的信息，然后针对所求的单个点 $(x,y)$ 进行查询即可。 特别地，这道题使用 逆向思维（倒序枚举） 会非常巧妙且高效：
- 接收并保存所有地毯的信息。
- 从最后一张铺设的地毯（即编号 $n$ 的地毯）开始，倒序向前遍历（一直到编号 $1$）。
- 对遇到的每一张地毯，检查点 $(x, y)$ 是否在它的覆盖范围内：
- 第一张满足条件的地毯，必定是所有覆盖该点的地毯中编号最大的，也就是处于最上面的地毯。
- 此时直接记录答案为该地毯编号，并使用
break提前终止循环即可（因为我们只需要找最上面的那一张）。
- 如果遍历完所有地毯都没有满足条件的，说明该点未被任何地毯覆盖，输出初始值
-1即可。
3. 复杂度分析
- 时间复杂度：$O(n)$。读取 $n$ 张地毯信息需要 $O(n)$ 的时间；查找答案时，最坏情况下（点被第一张地毯覆盖或未被覆盖）需要完整倒序遍历 $n$ 次，操作次数也是 $O(n)$ 级别。在 $n \le 10^4$ 的数据规模下，最大计算量仅在两万次左右，远远小于 C++ 1 秒内 $10^8$ 次的运行限制，效率极高。
- 空间复杂度：$O(n)$。不需要创建巨大的二维地图数组，只需要保存每张地毯的 $4$ 个参数即可。使用一个大小为 $10005 \times 4$ 的二维数组占用内存极小，完全满足轻量级空间限制的需求。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
// pos 数组用于存储地毯的信息
// pos[i][0], pos[i][1] 分别表示第 i 张地毯左下角的 x, y 坐标
// pos[i][2], pos[i][3] 分别表示第 i 张地毯在 x 轴和 y 轴方向的长度
int pos[10005][4];
int main() {
int n; // 地毯的总数 n
std::cin >> n;
// 依次读入每张地毯的信息，地毯编号从 1 到 n
for (int i = 1; i <= n; i++) {
std::cin >> pos[i][0] >> pos[i][1] >> pos[i][2] >> pos[i][3];
}
int x, y; // 所求地面的点的坐标 (x, y)
std::cin >> x >> y;
int ans = -1; // 记录所求的地毯的编号，如果没有被地毯覆盖则初始化输出 -1
// 从最后铺设的（也就是最上面的）地毯开始倒序遍历
// 只要找到第一个覆盖了点 (x, y) 的地毯，那就是覆盖该点的最上面的那张
for (int i = n; i >= 1; i--) {
// 判断点 (x, y) 是否在第 i 张地毯的覆盖范围内
// 即 x 坐标在 [a, a + g] 之间，y 坐标在 [b, b + k] 之间
if (x >= pos[i][0] && x <= pos[i][0] + pos[i][2] && y >= pos[i][1] &&
y <= pos[i][1] + pos[i][3]) {
ans = i; // 记录答案（即对应的地毯编号）
break; // 找到了最上面的那张，直接退出循环
}
}
// 输出结果，若没有地毯覆盖此处则会输出初始化时的 -1
std::cout << ans << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
