P3913. 车的攻击

发表于 分类于 阅读次数： Waline： 本文字数： 245 阅读时长 ≈ 1 分钟

考点

  • 排列组合

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e6 + 50;
int nx, ny, x[LEN], y[LEN];

int main() {
  int n, k, a, b;
  cin >> n >> k;
  while (k--) {
    cin >> a >> b;
    x[nx++] = a, y[ny++] = b;
  }
  sort(x, x + nx), sort(y, y + ny);
  nx = unique(x, x + nx) - x, ny = unique(y, y + ny) - y;
  cout << (1ll * n * n) - (1ll * (n - nx) * (n - ny));
  return 0;
}

思路

不同车之间影响的格子会有重复，秉持着正难则反的原则，考虑总格子数 - 不受影响的格子数

车的影响范围是当前整行与当前整列，所以不管有几个车、如何影响，不受影响的格子肯定也能拼成一个矩形

可以得到公式不受影响的格子数 = 不受影响的行数 * 不受影响的列数

但是棋盘长度高达1e9，不能常规采用一个bool类型的vis[1e9]数组去记录

考虑到车的个数只有1e6，所以选择给车的横纵坐标去重