学习笔记_25_03_14

Reference

• 题解 P3913 【车的攻击】

P3913 车的攻击

题目描述

$N \times N$ 的国际象棋棋盘上有$K$ 个车，第$i$个车位于第$R_i$行，第$C_i$ 列。求至少被一个车攻击的格子数量。

车可以攻击所有同一行或者同一列的地方。

输入格式

第1 行，2 个整数$N,K$。

接下来K 行，每行2 个整数$R_i,C_i$。

输出格式

1 个整数，表示被攻击的格子数量。

输入输出样例 #1

输入 #1

3 2
1 2
2 2

输出 #1

7

说明/提示

• 对于30% 的数据，$1 \le N \le 10^3; 1 \le K \le 10^3$；

• 对于60% 的数据，$1 \le N \le 10^6; 1 \le K \le 10^6$；

• 对于100% 的数据，$1 \le N \le 10^9; 1 \le K \le 10^6; 1 \le R_i , C_i \le N$。

解决方案

笔者的第一版代码是在硬抗庞大的数据规模的情况下头铁按照模拟棋盘的思路写出的，因此喜提10分…

if __name__ == "__main__":
    n, k = map(int, input().split())
    cars = []
    for i in range(k):
        x, y = map(int, input().split())
        cars.append((x, y))

    # 创建棋盘
    Map = [[0 for i in range(n)] for i in range(n)]

    for x, y in cars:
        for i in range(n):
            Map[x][i] += 1
            Map[i][y] += 1

    count = 0
    for i in range(n):
        for j in range(n):
            if Map[i][j] != 0:
                count += 1

    print(count)

因此显然这道题需要换一种角度思考，不妨就按Reference中题解给出的思路去理解。即使在不向一个方向平移车的情况下，我们依旧能够想象出其盲区的小格子的大致样子。与其尝试移动车，不如尝试将所有的零碎小格子拼成一块矩形，其面积与棋盘面积的差就是我们所要的答案。

两个相同的x值或y值显然只能对同一列造成影响，那么我们只需要统计一共有多少种不同的x值和y值即可。

那么最后要求的答案即为n * n - (n - count_x) * (n - count_y)。

c++题解如下所示（Python版本似乎由于语言的限制还是会爆TLE）：

#include <iostream>
#include <algorithm>
using namespace std;

const int K = 1000010;

long long xs[K], ys[K];

int main()
{
    long long n, k;
    cin >> n >> k;

    for (int i = 0; i < k; i++)
    {
        cin >> xs[i] >> ys[i];
    }

    // 开始计算坐标中不重复的点的个数
    sort(xs, xs + k);
    sort(ys, ys + k);

    long long count_x = 0, count_y = 0;

    for (int i = 0; i < k; i++)
    {
        if (xs[i] != xs[i+1])
        {
            count_x++;
        }
        if (ys[i] != ys[i+1])
        {
            count_y++;
        }
    }

    long long count = n * n - (n - count_x) * (n - count_y);
    cout << count;

    return 0;
}