ABC436C 2×2布局
ABC436C 2×2布局
【算法标签】 数据结构/哈希表/坐标编码
【语法标签】 :unordered_set、for循环、坐标编码
在一个 的网格上(),依次进行 次操作()。
第 次操作为:以 为左上角,放置一个 的方块(占据 4 个格子)。如果这个方块与已放置的任何方块有重叠(共享至少一个格子),则跳过不放置。
求最终网格上方块的总数。
二、解题思路
2.1 数据规模分析
| 参数 | 范围 | 含义 |
|---|---|---|
| 网格边长,巨大——不能开二维数组 | ||
| 操作次数,可以接受 |
高达 ,意味着不可能真的维护一个 的网格。好在 只有 ,我们只需要记录已经放置了哪些方块即可。
2.2 核心问题:如何判断两个方块是否重叠
两个 的方块,左上角分别在 和 。
方块 1 占据的行:,列:
方块 2 占据的行:,列:
它们不重叠的条件是(在行或列上完全分离):
(方块 1 在方块 2 上方,行不挨着)
或 (方块 2 在方块 1 上方)
或 (方块 1 在方块 2 左边)
或 (方块 2 在方块 1 左边)
反过来,重叠的条件是以上四条都不成立,即:
且 且 且
进一步简化: 且
翻译成人话:两个 方块重叠,当且仅当它们的左上角坐标在行和列上的差距都不超过 1。
2.3 算法设计
用一个哈希集合(unordered_set)存放所有已放置方块的左上角坐标。
为了能直接用 unordered_set 存储坐标,我们将坐标 编码为一个 long long 整数:
由于 BASE 比 c 的最大可能值()大,不同的 一定对应不同的 key,就像把二维表格的每个格子在脑子里编了一个唯一的序号。
对于每次操作 ,检查是否与已放置的方块冲突。根据上面的结论,只需检查集合中是否存在左上角在以下范围内的方块:
- 行范围:(共 3 种可能)
- 列范围:(共 3 种可能)
- 即检查 个位置
(R-1, C-1) (R-1, C) (R-1, C+1)
(R, C-1) (R, C) (R, C+1)
(R+1, C-1) (R+1, C) (R+1, C+1)如果这 9 个位置没有一个在集合里 → 不冲突 → 放置方块,将 加入集合,答案 +1。
只要有一个在集合里 → 冲突 → 跳过。
2.4 手动模拟样例
样例 1:
初始:集合为空
操作1: (1,1)
检查 3×3 范围:(0,0)~(2,2),都不在集合中
→ 放置!集合 = {(1,1)},ans = 1
操作2: (2,2)
检查:
(1,1) → 在集合中!冲突!
→ 跳过
操作3: (2,3)
检查:(1,2)(1,3)(1,4)(2,2)(2,3)(2,4)(3,2)(3,3)(3,4)
都不在集合中 → 放置!集合 = {(1,1), (2,3)},ans = 2
答案:2样例 2:
操作1: (1,1) → 放置,ans=1
操作2: (1,101) → 距离很远,不冲突 → 放置,ans=2
操作3: (101,1) → 不冲突 → 放置,ans=3
操作4: (101,101) → 不冲突 → 放置,ans=4
答案:4注意到 达到 10 亿,但集合中只存了 4 个坐标,完全不受网格大小影响。
2.5 为什么不开二维网格
如果开 int grid[1000000000][1000000000]:
- 需要约 字节 4 亿 GB 内存 → 不可能
所以我们只存有方块的位置(稀疏存储),最多 个方块,集合里最多 个条目,在内存范围内。
2.6 用哈希集合加速
题目数据范围 ,使用 set(红黑树)每次查找 O(log M),虽然理论可行,但常数因子较大,极端数据下容易超时。
改用 unordered_set(哈希表),查找近似 O(1),大幅减少常数。
问题:unordered_set 不能直接存 pair<int, int>(需要自己写哈希函数)。解决方案是把坐标编码成 long long。
坐标编码的思想
核心想法:把二维坐标"压缩"成一维整数,就像把一张表格的每个格子编上序号。
假设你有一个 的表格:
列: 0 1 2 3
行0: (0) (1) (2) (3)
行1: (4) (5) (6) (7)
行2: (8) (9) (10) (11)单元格 的编号怎么算?先跳过前面 r 整行,再加上本行的偏移 c:
验证:,也就是第 6 号格子。✅
为什么 BASE 取
本题中,行和列的范围都是 (即 N)。
用同样的公式:
关键在于 BASE 必须大于 c 的最大值。因为:
- c 最大是
- 如果 BASE = ,那么 和 的 key 差 1,不会重叠
- 但等一下——如果 BASE = ,那么 的 key = ,而 的 key = ,冲突了!
所以更安全的写法是 BASE 取 或更大。代码中用了 1000000000LL(即 ),实际上因为本题 (坐标从 1 开始),不会出现 的情况,所以不会冲突。但为了万无一失,这里更新为 :
const long long BASE = 1000000007LL; // 比 10^9 大一点,确保不冲突
long long key = (long long)r * BASE + c;为什么这就能代替 pair?
pair<int, int> 本质上就是把两个 int 绑在一起。unordered_set 不知道怎么对 pair 算哈希值(除非你给它写规则)。但 long long 是单个整数,unordered_set<long long> 原生支持。
编码之后:
- 每个不同的 → 唯一的一个
long long(单射/一一映射) - 反过来,同一个 key 不可能对应两个不同的坐标(因为 BASE > c 的最大值)
这就等价于把 pair 存进去了,但绕开了写哈希函数的麻烦。
// 不用这样(需要额外写哈希函数):
unordered_set<pair<int, int>> blocks; // ❌ 编译不过
// 而是这样:
unordered_set<long long> blocks; // ✅ 原生支持
blocks.insert((long long)r * BASE + c);三、参考代码
#include <bits/stdc++.h>
using namespace std;
const long long BASE = 1000000007LL; // 比 N 大,用于编码坐标(确保不同 (r,c) 不冲突)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
unordered_set<long long> blocks; // 已放置方块的左上角坐标(编码后)
int ans = 0;
while (m--) {
int r, c;
cin >> r >> c;
// 检查 3×3 范围内是否有已放置的方块
bool conflict = false;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr;
int nc = c + dc;
long long key = (long long)nr * BASE + nc;
if (blocks.count(key)) {
conflict = true;
break; // 找到冲突,提前退出内层循环
}
}
if (conflict) break; // 提前退出外层循环
}
if (!conflict) {
long long key = (long long)r * BASE + c;
blocks.insert(key);
ans++;
}
}
cout << ans << endl;
return 0;
}代码要点
| 写法 | 说明 |
|---|---|
unordered_set<long long> | 哈希表,查找 O(1) |
BASE = 1000000007LL | 编码系数,比 N 大,保证 唯一映射 |
key = nr * BASE + nc | 将二维坐标编码成一维整数 |
blocks.count(key) | 检查坐标是否在集合中 |
blocks.insert(key) | 将新方块加入集合 |
双重 for + break | 检查 9 个位置,一旦发现冲突就跳出 |
set vs unordered_set
为什么这里用 unordered_set 而非 set?
set是红黑树,查找 O(log M),对于 M=2×10^5 来说每次查找约 18 次比较unordered_set是哈希表,查找近似 O(1),常数因子小得多unordered_set不能直接存pair<int, int>,所以用long long编码绕过去
在本题极端数据下,set 的 O(log M) 常数可能超时,unordered_set 是更安全的选择。
四、复杂度分析
| 项目 | 复杂度 | 说明 |
|---|---|---|
| 时间 | 期望 | 每次操作最多检查 9 个位置,哈希查找 O(1) |
| 空间 | 哈希表中最多存 个坐标 |
, 次哈希查找,每次 O(1),轻松通过。
五、知识扩展
5.1 常用集合操作
set(有序集合,红黑树):
set<int> s;
s.insert(3); // 插入,O(log n)
s.erase(3); // 删除,O(log n)
s.count(3); // 是否存在(返回 0 或 1),O(log n)
s.size(); // 元素个数
s.clear(); // 清空
// 有序遍历(从小到大)
for (auto x : s) {
cout << x << endl;
}unordered_set(无序集合,哈希表):
unordered_set<int> s;
s.insert(3); // 插入,O(1) 期望
s.erase(3); // 删除,O(1) 期望
s.count(3); // 是否存在(返回 0 或 1),O(1) 期望
// 遍历(无序)
for (auto x : s) {
cout << x << endl;
}set | unordered_set | |
|---|---|---|
| 底层结构 | 红黑树 | 哈希表 |
| 查找/插入/删除 | O(log n) | O(1) 期望 |
| 遍历顺序 | 从小到大 | 无序 |
支持 pair | ✅ 开箱即用 | ❌ 需自写哈希 |
什么时候用哪个?
- 需要有序遍历 →
set - 追求速度、不关心顺序 →
unordered_set(但注意哈希冲突最坏会退化到 O(n)) - 要存
pair又不想写哈希 →set,或者像本题一样把坐标编码成整数
5.2 pair 用法
pair<int, int> p = {1, 2};
cout << p.first << ' ' << p.second << endl; // 1 2pair 自带比较规则:先比 first,first 相同再比 second。所以可以直接放进 set。
5.3 换个思路:存四个格子
也可以不推导「3×3 邻域」规则,而是直接存每个方块占据的 4 个格子坐标。每次检查时查 4 个格子是否存在。
unordered_set<long long> occupied; // 所有被占据的格子
const long long BASE = 1000000007LL;
// 检查新方块的 4 个格子是否被占
bool conflict = false;
for (int dr = 0; dr <= 1; dr++)
for (int dc = 0; dc <= 1; dc++) {
long long key = (long long)(r + dr) * BASE + (c + dc);
if (occupied.count(key))
conflict = true;
}
if (!conflict) {
for (int dr = 0; dr <= 1; dr++)
for (int dc = 0; dc <= 1; dc++) {
long long key = (long long)(r + dr) * BASE + (c + dc);
occupied.insert(key);
}
ans++;
}两种方法等价,但「存左上角 + 查 9 个邻域」空间更省( 个 vs 个)。
六、易错点
开不了数组:,必须用稀疏存储(
set/unordered_set/map),不能int grid[N][N]。break只跳一层:双重循环中内层 break 只退出内层,外层需要再判断一次。代码中用了if (conflict) break;在外层再 break。重复操作:同一坐标可能出现多次(样例 3 中
(6,1)出现两次),第二次直接检测到冲突跳过,代码自动处理。
