P3913 车的攻击

摘要：N×N 的国际象棋棋盘上有K个车，第i个车位于第R[i]行，第C[i]列。求至少被一个车攻击的格子数量。

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

看起来挺简单，看到数据范围了吗？看到了：对于100% 的数据，N1≤N≤109;1≤K≤106;1≤Ri?,Ci?≤N。

死心了吗？是真的有点绝望。第一反应就是：桶，那反正也想不出别的办法了，我们就用桶试试吧。

经过画图推算之后，我们可以得到一个公式：(n*n)-(n-chang)*(n-clie)

n是棋盘的边长，chang是有几行被攻击了（不算重复的），clie是有几列被攻击了（也不算重复的）

推算过程：n-chang是算有几行没有被攻击，n-clie是算有几列没有被攻击，把这两个相乘就可以得到没有被车攻击的面积。

再用n*n（也就是棋盘的总面积）减去没有被车攻击的面积，就可以得到被车攻击的面积了。

代码如下：

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
long long hang[1000010],lie[1000010];//开大点总没坏处
long long n,k,a,b,chang=0,clie=0;
int main(){
    scanf("%lld%lld",&n,&k);//用scanf和printf会更快点
    for(int i=0;i<k;i++){
        scanf("%lld%lld",&a,&b);
        if(hang[a]!=1){
            chang++;
            hang[a]=1;
        }
        if(lie[b]!=1){
            clie++;
            lie[b]=1;
        }//用桶来标记，如果这一列是第一次被攻击那么就让clie++，如果这一行是第一次被攻击那么就让chang++
    }
    printf("%lld",(n*n)-((n-chang)*(n-clie)));//公式
}

评测结果：60分，有4个点RE了

嗯，进步了，那就让我们接着优化。

既然RE是因为桶，那么我们就想个能把桶替换掉的办法

这次还是要请出我们的救星——sort

先输入，然后用sort排序，最后再用for循环遍历判断。

因为sort一遍后他会大小排序，然后我们用for循环遍历判断前一个数如果不同于后面一个数（也就是有没有算过的行或列），就让chang或clie++，最后再套用公式，就可以解决桶RE的问题了。

AC代码如下：

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
long long hang[1000010],lie[1000010];
long long n,k,a,b,chang=0,clie=0;
int main(){
    scanf("%lld%lld",&n,&k);//用scanf和printf读入和输出会更快点
    for(int i=0;i<k;i++){
        scanf("%lld%lld",&hang[i],&lie[i]);
    }
        //分别把行和列sort一遍
    sort(hang,hang+k);
    sort(lie,lie+k);
    for(int i=0;i<k;i++){//循环遍历判断
        if(hang[i]!=hang[i+1]){//如果发现没有被攻击过的行，就让chang++。
            chang++;
        }
        if(lie[i]!=lie[i+1]){//如果发现没有被攻击过的列，就让clie++。
            clie++;
        }
    }
    printf("%lld",(n*n)-((n-chang)*(n-clie)));//套用公式，输出
}