题解 P3913 【车的攻击】

· · 题解

P3913 车的攻击 题解

这是蒟蒻做的第100道橙题，准备发个题解庆祝一下，求管理大大通过，我一定会尽我所能讲的详细的！

废话不多说正式开始

看到这题当然最先想到DFS啦~

DFS大致思路如下

Solution 1 30pts

当然，从我开始写代码的时候，我就意识到了DFS绝对会RE（因为我的一个好习惯，详见代码）

也希望大家都能有这个习惯，不要写完代码，蓦然回首，RE就在灯火阑珊处

不过，为了能写出一篇好的题解，干了兄弟们

应该没人不会DFS了吧，就不讲了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1010;//那个好习惯

int n,k;
int map[N][N];
int attack[N][N];
int nx[15]={0,0,1,0,-1};
int ny[15]={0,-1,0,1,0};

void dfs(int x,int y,int dir)
{
    int xx=x+nx[dir];
    int yy=y+ny[dir];
    attack[x][y]=1;
    if (xx>=1&&xx<=n&&yy>=1&&yy<=n&&map[xx][yy]==0)
    {
        dfs(xx,yy,dir);
    }
}

int main()
{
    scanf("%d%d,",&n,&k);
    for (int i=1;i<=k;i++)
    {
        int r,c;
        scanf("%d%d",&r,&c);
        map[r][c]=1;
        attack[r][c]=1;
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (map[i][j]==1)
            {
                for (int k=1;k<=4;k++)
                {
                    dfs(i,j,k);
                }
            }
        }
    }
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (attack[i][j]==1)
            {
                cnt++;
            }
        }
    }
    printf("%d",cnt);
    return 0;
}

结果如何？

30分，AC#1#2#3，其余RE

很明显，题目中说n\le10^9,在将数据存储到map数组的过程中一定会RE，所以考虑另一种解法。

说句闲话：暴搜不RE，数据太垃圾

solution 2 100pts

注意：

Part 1

首先，我们考虑任意两枚棋子都不在同一行，同一列的情况下。

你有一个棋盘

因为无聊，你在上面添加了一个小小的车。

如图，灰色的是棋盘，深蓝是可覆盖的行，浅蓝是可覆盖的列。

注：多余的两条蓝色框是为了加强读者理解为什么覆盖的范围总是2n-1，如不理解可以跳过。

此时，不管这枚小小的车怎么移动，他所能攻击到的范围都是2n-1(好好思考一下这句话)。之前好像剧透了

为了使我们的思路保持有规律，我们把它放到第一行第一列

由于你现在仍然很无聊，所以你想要再加入一枚车。

同样地，不管这两枚棋子放在什么位置(但要满足不在同一行，同一列)，他们总会有重合，并且重合部分面积总是为2(自行理解，建议自己画几张图试试)。

你发现，它可以放在任何不在第一行，也不再第一列的任何位置(因为第一行/列已经被第一个车占用)。

为了保持规律，我们把它放在第二行第二列。

现在你发现了什么？

这两个车穿的是情侣装！

当棋盘上有2枚不同行不同列的车时，可覆盖的区域为n^2-(n-2)^2。

同样地，当棋盘上有x枚不同行不同列的车时，未覆盖的区域为n^2-(n-x)^2。

Part 2

接下来，我们就要考虑有重复行/列。的问题了。

一个格子能放下两枚车吗？当然不行。

所以，任意两枚棋子只有可能行相同或列相同，绝不可能行列都相同。

由于行和列在本题中本质上是没有区别的，所以我们现在以列举栗子。

如图，由于第三个车与第二个车在同一列，所以那重复的一列只计算了一次

我们发现，重复的行/列坐标是不计算的。

所以，我们可以在r数组和c数组中去掉重复的，只保留独一无二的，然后计算有多少个独一无二的，我们假设：

x行，y列是独一无二的时候，则可覆盖的面积为：n^2-(n-x)×(n-y)

搞了半天，这就是个去重的题啊~

只要输入之后算一下r里有几个重的，c里有几个重的，都去掉，最后计数器统计一下然后套公式输出就得了呗~

注意：cnt在这里的最大值是整个棋盘都可覆盖，为10^{18}，所以不开longlong见祖宗

Part 3

Code:

这篇代码说是去重并不准确，应该说是“计不重”，直接sort排序后记录有数组中多少个不同的元素

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int K=1000010;

long long r[K],c[K];

int main()
{
    long long n,k;
    scanf("%lld%lld",&n,&k);
    for (int i=1;i<=k;i++)
    {
        scanf("%lld%lld",&r[i],&c[i]);
    }
    //排序是为了后面计重 
    sort(r+1,r+k+1);
    sort(c+1,c+k+1);
    long long cntr=0,cntc=0;
    for (int i=1;i<=k;i++)
    {
        if (r[i]!=r[i+1]) 
        {
            cntr++;//r里面有多少个独一无二的 
        }
        if (c[i]!=c[i+1])
        {
            cntc++;//同上 
        }
    }
    printf("%lld",n*n-(n-cntr)*(n-cntc));
    return 0;
}

毕竟我是蒟蒻，如果有问题请dalao一定指出！