题解：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)，由于巨大的空间需求，无法通过。

于是，我们想到，利用 map 记录下所有能被马攻击的坐标 （包括马所在位置），最后进行计算即可。

最坏空间复杂度 \mathcal{O}(M)，时间复杂度 \mathcal{O}(M \log_2 M)，可以通过。（1\leq M\leq2\times10^5）

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

时间复杂度为 \mathcal{O}(M \log_2M)。

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

:::warning[注意]{open}

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

代码实现

#include <bits/stdc++.h>
#define int long long
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：

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

update 2026.07.29：

  • 删除了大量重复内容，修改表述。