自动搬运

查看原文

来自洛谷，原作者为

	Billhqh9 Just be happy.

搬运于2025-08-24 23:09:08，当前版本为作者最后更新于2025-02-01 18:28:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

洛谷

朴素法

思路：

我们先按题目中说的，用二维数组记录下每个棋子可以攻击到的位置，最后做一个统计。时间复杂度：$O(mn+n^2)$，可以通过此题。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
int n, m, ans;
bool board[maxn][maxn];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        board[x][y] = true;
        if(c == 'N') {
            if(x - 2 >= 1 && y - 1 >= 1)
                board[x - 2][y - 1] = true;
            if(x - 2 >= 1 && y + 1 <= n)
                board[x - 2][y + 1] = true;
            if(x - 1 >= 1 && y - 2 >= 1)
                board[x - 1][y - 2] = true;
            if(x - 1 >= 1 && y + 2 <= n)
                board[x - 1][y + 2] = true;
            if(x + 2 >= 1 && y - 1 >= 1)
                board[x + 2][y - 1] = true;
            if(x + 2 >= 1 && y + 1 <= n)
                board[x + 2][y + 1] = true;
            if(x + 1 >= 1 && y - 2 >= 1)
                board[x + 1][y - 2] = true;
            if(x + 1 >= 1 && y + 2 <= n)
                board[x + 1][y + 2] = true;
        }
        if(c == 'R') {
            for(int x1 = x, y1 = y; x1 >= 1; --x1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 <= n; ++x1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; y1 >= 1; --y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; y1 <= n; ++y1)
                board[x1][y1] = true;
        }
        if(c == 'Q') {
            for(int x1 = x, y1 = y; x1 >= 1; --x1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 <= n; ++x1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; y1 >= 1; --y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; y1 <= n; ++y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 >= 1 && y1 >= 1; --x1, --y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 >= 1 && y1 <= n; --x1, ++y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 <= n && y1 >= 1; ++x1, --y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 <= n && y1 <= n; ++x1, ++y1)
                board[x1][y1] = true;
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(board[i][j] == true)
                ++ans;
    cout << ans << endl;
    return 0;
}

优化法

虽然 AC 了，我们再来想想能不能继续优化。

思路

再使用多个数组记录攻击信息，直接花 $O(1)$ 时间记录行、列、对角线的攻击信息，避免枚举攻击的点。比如用 $f1_i$ 表示第 $i$ 行是否被攻击。这样节省枚举攻击的点的时间，可将时间复杂度的第一项优化一维。时间复杂度：$O(m+n^2)$。

优化代码

注：在我的代码中 $f1_i$ 表示第 $i$ 行是否被攻击；$f2_i$ 表示第 $i$ 列是否被攻击；$f3_i$ 表示第 $i$ 条从左上往右下的对角线是否被攻击；$f4_i$ 表示第 $i$ 条从右上往左下的对角线是否被攻击。在这里 $f1_i$ 和 $f2_i$ 不用说，但要讲讲在知道坐标的情况下如何算出 $f3_i$ 和 $f4_i$ 中的 $i$。

对于每条从左上往右下的对角线上的每个坐标为 $(x,y)$ 的点，我们可以发现：$x-y$ 为定值，且每条这样的对角线 $x-y$ 的值都不同。所以计算 $i$ 可以从 $x-y$ 入手，找规律后发现 $i$ 可以表示为 $x-y+n$。同理，我们可以发现：对于每条从右上往左下的对角线上的每个坐标为 $(x,y)$ 的点，$x+y$ 为定值，且每条这样的对角线 $x+y$ 的值都不同。所以，找规律后发现 $i$ 可以表示为 $x+y-1$。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
int n, m, ans;
bool board[maxn][maxn], f1[maxn], f2[maxn], f3[maxn * 2], f4[maxn * 2];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        board[x][y] = true;
        if(c == 'N') {
            if(x - 2 >= 1 && y - 1 >= 1)
                board[x - 2][y - 1] = true;
            if(x - 2 >= 1 && y + 1 <= n)
                board[x - 2][y + 1] = true;
            if(x - 1 >= 1 && y - 2 >= 1)
                board[x - 1][y - 2] = true;
            if(x - 1 >= 1 && y + 2 <= n)
                board[x - 1][y + 2] = true;
            if(x + 2 >= 1 && y - 1 >= 1)
                board[x + 2][y - 1] = true;
            if(x + 2 >= 1 && y + 1 <= n)
                board[x + 2][y + 1] = true;
            if(x + 1 >= 1 && y - 2 >= 1)
                board[x + 1][y - 2] = true;
            if(x + 1 >= 1 && y + 2 <= n)
                board[x + 1][y + 2] = true;
        }
        if(c == 'R') {
            f1[x] = true;
            f2[y] = true;
        }
        if(c == 'Q') {
            f1[x] = true;
            f2[y] = true;
            f3[x - y + n] = true;
            f4[x + y - 1] = true;
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(board[i][j] == true || f1[i] == true || f2[j] == true || f3[i - j + n] == true || f4[i + j - 1] == true)
                ++ans;
    cout << ans << endl;
    return 0;
}

两份代码虽然都能过，但明显第二份代码更快。