题解 P3913 【车的攻击】

Kater_kcl · 2019-09-18 00:14:17 · 题解

本题数据已增强，但是做法不变，仅将读入和输出换成stdio的即可

题解好少啊，赶紧水一波。

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

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

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

不难看出，交叉点的个数就是有车的行数*有车的列数，那么就不难导出公式：

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

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

然后值得注意的有两点：
第一点：在unique之前必须保证去重数组有序，也就是得sort一下。
第二点：unique并不会生成一个新的数组，而是将原数组多余的部分“移”到了数组之后，同时unique本身还会返回一个指针，指向去重之后的最后一位。

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

下面放ac代码

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#define ll long long
const int maxn=1e6+5;
using namespace std;
ll n,k;
ll x[maxn],y[maxn];
int main(){
 //       freopen("test.in","r",stdin);
        //cin>>n>>k;
        scanf("%lld%lld",&n,&k);
        for(ll i=0;i<k;i++){
                //cin>>x[i]>>y[i];
            scanf("%lld%lld",&x[i],&y[i]);
        }
        sort(x,x+k);
        sort(y,y+k);
        ll sizex=unique(x,x+k)-x;
        ll sizey=unique(y,y+k)-y;
        //cout<<n*n-(n-sizex)*(n-sizey);
        printf("%lld",n*n-(n-sizex)*(n-sizey));
        return 0;
}

很简短对不对，嘻嘻。