题解：AT_abc377_c [ABC377C] Avoid Knight Attack

· · 题解

题目传送门

题目大意

有一个 N 行 N 列的网格，每个方格要么是空的，要么有一个“马”放在上面。网格上有 M 个棋子，第 k 个棋子被放置在 (a_k,b_k)。

例如，放在 (4,4) 位置上的棋子可以吃掉八个方向上的棋子：

有多少个不会被马吃掉的棋子？

题目分析

我们发现，这道题目是前一题的加强版，可以用二维数组记录被马吃掉的位置。
但是，我们发现 N\leq10^9，很明显，直接记录数组，空间复杂度 \mathcal{O}(N^2)，时间复杂度 \mathcal{O}(M)，由于巨大的空间需求，无法通过。

空间复杂度：
对于开一个 N\times N 的数组，不难得出时间复杂度为 \mathcal{O}(N^2)。

时间复杂度：
输入并标记 M 个位置，每个位置扩展出最多 8 个点，可以同时计算，总用时 \mathcal{O}(M)。

于是，我们想到，利用 map 记录下所有能被马攻击的坐标 （包括马所在位置），最后进行计算就可以啦！
最坏空间复杂度 \mathcal{O}(M)，时间复杂度 \mathcal{O}(M \log_2 M)，可以通过。（1\leq M\leq2\times10^5）

空间复杂度： 对于一个存储 M 个元素的双下标 map，每个位置有 3 个元素，空间复杂度为 \mathcal{O}(M)。

时间复杂度：

  • 输入 M 个数，用时 \mathcal{O}(M)；
  • 每次扩展 8 个方向，用时 \mathcal{O}(1)；
  • 每次插入 map，用时 \mathcal{O}(\log_2M)。

综上所述，时间复杂度为 \mathcal{O}(M \log_2M)。

我们可以打出八个方向的表，边输入边记录排除的格子。

Q：如何使用 map 记录二维坐标？\ A：使用 map 套用 pair。

代码有一些细节，需要注意： :::warning[注意]{open}

具体介绍请看代码中的注释。

代码实现

#include <bits/stdc++.h>
#define int long long // 提示：答案可能是2^32或更大
using namespace std;

map <pair <int, int>, bool> a; // 记录(x, y)位置放置棋子，是否能被马吃掉

int n, m, x, y;
int fx[] = {0, 2, 1, -1, -2, -2, -1,  1,  2}; // 打8个方向的表
int fy[] = {0, 1, 2,  2,  1, -1, -2, -2, -1};

signed main() {
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        cin >> x >> y;
        a[make_pair(x, y)] = 1; // 注意：要记录马的所在位置
        for (int j = 1;j <= 8;j++) // 枚举8个方向
            if (x + fx[j] > 0 && y + fy[j] > 0 && x + fx[j] <= n && y + fy[j] <= n) // 特判：防止坐标越界
                a[make_pair(x + fx[j], y + fy[j])] = 1; // 将这个位置设为可被吃掉
    }
  // 进行数学运算：所有格子-可攻击格子=剩余格子，a.size()代表 map 中被使用过的格子数
    cout << n * n - a.size() << endl; 
    return 0;
}

update 2024.11.4：

  • 对于时空复杂度的计算做详细介绍。

update 2025.07.29：

  • 由于洛谷编辑器更新，优化题解格式；
  • 优化了时空复杂度计算，删除了常数部分。

To 管理员：由于表述需要，因此使用折叠框，请不要介意。