P3913 车的攻击

题目传送门

题目要咱求能被攻击到的格子,但是如果硬处理的话超时是妥妥的,所以咱得想个数学办法,不能只靠模拟来打暴力。

首先考虑能不能直接将(x)轴与(y)轴有车的点先全部记录下来,然后将有车的行的数量和有车的列的数量记录下来,然后*(n)再相加,但是这样显然不可行,因为这样会导致在行列交汇处的点呗重新算(2)次。

既然被重新计算了,那我们把他们都删掉不就可以了吗?

不难看出,交叉点的个数就是有车的行数*有车的列数,那么就不难导出公式:
逆向思维,反着想,先找出所有不能被攻击的点,总的点数减去不能被攻击的点数,就是最少被一个车攻击的点数啦!
(ans=n^2-(n-x) imes (n-y))

然后就是统计一共有几行几列有车了,这里就要用到我大(stl)中的一员大将:(unique),也就是去重,通俗来讲,这个玩应的用法一般是

(unique)(数组名,数组名+大小)
(没错和(sort)几乎一模一样)

然后值得注意的有两点:
第一点:在(unique)之前必须保证去重数组有序,也就是得(sort)一下。

第二点:(unique)并不会生成一个新的数组,而是将原数组多余的部分“移”到了数组之后,同时(unique)本身还会返回一个指针,指向去重之后的最后一位。

利用(c++)可以指针相加减的特点,我们可以通过 (unique)-数组指针 来知道去重之后数组的“大小”(这里听不懂没关系,往下看代码,背住用法就好)

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e6 + 10;

LL n; //棋盘长、宽
int k; //注意这里要使用LL,使用int会有部分测试点WA,
// 原因是后面的去重返回的是LL,如果这里有int,应该是会自动降为int导致出问题。

//行数组与列数组
int r[N], c[N];

int main() {
    //加快读取速度
    ios::sync_with_stdio(false);
    cin.tie();
    //棋盘的长宽和车的个数
    cin >> n >> k;
    //读入车的位置
    for (int i = 1; i <= k; i++) cin >> r[i] >> c[i];
    //排序
    sort(r + 1, r + k + 1);
    sort(c + 1, c + k + 1);
    //去重
    LL x = unique(r + 1, r + k + 1) - r - 1;
    LL y = unique(c + 1, c + k + 1) - c - 1;

    printf("%lld", n * n - (n - x) * (n - y));
    return 0;
}
原文地址:https://www.cnblogs.com/littlehb/p/15184867.html