ABC370D Cross Explosion

Tag：模拟

题目描述

有一个网格，网格中有 \(H\) 行和 \(W\) 列。让 \((i, j)\) 表示从上往下数第 \(i\) 行，从左往上数第 \(j\) 列的单元格。
最初，每个单元格中都有一面墙。
按照下面给出的顺序处理 \(Q\) 个查询后，求剩余墙的数量。

在 \(q\) -th 查询中，我们给出了两个整数 \(R_q\) 和 \(C_q\) 。
您在 \((R_q, C_q)\) 处放置炸弹摧毁墙壁。结果发生了以下过程。

如果在 \((R_q, C_q)\) 处有一堵墙，则摧毁这堵墙并结束进程。
如果 \((R_q, C_q)\) 处没有墙壁，则摧毁从 \((R_q, C_q)\) 向上、向下、向左、向右观察时出现的第一面墙壁。更确切地说，以下四个过程是同时进行的：
- 如果存在一个 \(i \lt R_q\) ，使得在 \((i, C_q)\) 处有一堵墙，而在所有 \(i \lt k \lt R_q\) 的 \((k, C_q)\) 处都没有墙，则摧毁 \((i, C_q)\) 处的墙。
- 如果存在一个 \(i \gt R_q\) ，使得在所有 \(R_q \lt k \lt i\) 中， \((i, C_q)\) 处有一堵墙，而 \((k, C_q)\) 处没有墙，则破坏 \((i, C_q)\) 处的墙。
- 如果存在一个 \(j \lt C_q\) ，使得在所有 \(j \lt k \lt C_q\) 中， \((R_q, j)\) 处有一堵墙，而 \((R_q, k)\) 处没有墙，则摧毁 \((R_q, j)\) 处的墙。
- 如果存在一个 \(j \gt C_q\) ，使得在 \((R_q, j)\) 处有一堵墙，而在所有 \(C_q \lt k \lt j\) 的 \((R_q, k)\) 处都没有墙，则摧毁 \((R_q, j)\) 处的墙。

数据说明：

\(1 \leq H, W\)
\(H \times W \leq 4 \times 10^5\)
\(1 \leq Q \leq 2 \times 10^5\)
\(1 \leq R_q \leq H\)
\(1 \leq C_q \leq W\)

分析

其实就是按照题目的意思来硬模拟，存墙的部分可以使用 \(set\) 来存，删除的时候直接 \(erase\)。

本题值得注意的一个点是，我们在 \(set\) 使用 \(lower\_bound\) 的时候，记得使用 \(set\) 自带的 \(lower\_bound\)， \(std::lower\_bound\) 在 \(set\) 上进行二分的时候会退化到线性，会超时。

代码实现

void NeverSayNever() {
    int n, m; cin >> n >> m;
    vector<set<int>> row(n), col(m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            row[i].insert(j);
            col[j].insert(i);
        }
    }
    int q; cin >> q;
    int ans = n * m;
    while (q--) {
        int r, c; cin >> r >> c;
        r -= 1, c -= 1;
        if (row[r].contains(c)) {
            ans -= 1;
            row[r].erase(c);
            col[c].erase(r);
        } else {
            auto it1 = row[r].lower_bound(c);
            auto it2 = col[c].lower_bound(r);
            if (it1 != row[r].begin()) {
                int tmp = *prev(it1);
                ans -= 1;
                row[r].erase(tmp);
                col[tmp].erase(r);
            }
            if (it1 != row[r].end()) {
                int tmp = *it1;
                ans -= 1;
                row[r].erase(tmp);
                col[tmp].erase(r);
            }
            if (it2 != col[c].begin()) {
                int tmp = *std::prev(it2);
                ans -= 1;
                row[tmp].erase(c);
                col[c].erase(tmp);
            }
            if (it2 != col[c].end()) {
                int tmp = *it2;
                ans -= 1;
                row[tmp].erase(c);
                col[c].erase(tmp);
            }
        }
    }
    cout << ans << endl;
}

日志

本页面创建于 2024/09/09 11:26