车的攻击

题意

在 n*n 棋盘上放若干车，统计至少被一辆车所在行或所在列覆盖的格子数。

思路

只需知道有多少个不同的被攻击行 R 和列 C。所有行覆盖 R*n 个格子，所有列覆盖 C*n 个格子，行列交叉的 R*C 个格子被重复计算一次，因此答案是：

Rn+Cn-RC

车的位置可能重复行或重复列，分别用集合去重。

Python 知识

set.add 自动忽略重复行列编号。
len(rows)、len(columns) 就是容斥公式所需的集合大小。
逐行读取百万个车，避免一次性 token 列表带来的峰值内存。
Python 大整数可直接容纳 n<=1e9 的棋盘计数。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：集合成员去重。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：大规模逐行输入。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20import sys


def main():
    read = sys.stdin.buffer.readline
    n, rook_count = map(int, read().split())
    rows = set()
    columns = set()
    for _ in range(rook_count):
        row, column = map(int, read().split())
        rows.add(row)
        columns.add(column)

    attacked_rows = len(rows)
    attacked_columns = len(columns)
    print(n * attacked_rows + n * attacked_columns - attacked_rows * attacked_columns)


if __name__ == "__main__":
    main()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/**
 * P3913 车的攻击
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int rows[MAXN], cols[MAXN];
int n, k;

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d", &rows[i], &cols[i]);
    }
    sort(rows + 1, rows + k + 1);
    sort(cols + 1, cols + k + 1);
    // 去重后统计不同行数和列数
    int row_cnt = unique(rows + 1, rows + k + 1) - (rows + 1);
    int col_cnt = unique(cols + 1, cols + k + 1) - (cols + 1);
    // 被攻击格子数 = 行 * n + 列 * n - 行 * 列
    long long ans = 1LL * row_cnt * n + 1LL * col_cnt * n - 1LL * row_cnt * col_cnt;
    printf("%lld\n", ans);
    return 0;
}

复杂度

期望时间复杂度 $O(k)$ ，空间复杂度 $O(k)$ 。

总结

棋盘虽然巨大，但覆盖只由行集合和列集合决定；集合去重加两集合容斥即可。

目录

题意

思路

Python 知识

代码

复杂度

总结