题目链接

1.技巧总结

1.1 n进制降维

本题地雷坐标的x，y取值范围过大$( 0≤x,y≤10^9 )$，如果直接把x，y当作下标会爆数组。因此我们可以通过将二维数对{x,y}看作是一个$10^9+1$进制数，高位是x，低位是y，有$(xy)_{10^9+1}=x\times(10^9+1)+y$,于是我们便将一组二维数对{x,y}映射成了一维唯一值，从而达到了编码和降维的目的。

1.2 手写哈希

由于本题数据范围过大，我们如果使用STL中的unordered_map<typename,typename>或者map<typename,typename>在本题中都会有超时风险，于是我们便可以考虑手写哈希函数(据说速度是map的十倍左右)。

1.2.1 哈希模板-开放寻址法（写法较为固定）

int find(LL x)
{
    int t = (x % M + M) % M;
    while(hash1[t]!=-1&&hash1[t]!=x)
    {
        t++;
        if(t==M) t=0;
    }
    return t;
}

1.3 深度优先搜索-DFS

由于本题每个地雷或者排雷火箭的引爆，会导致其范围内的其他地雷连锁引爆，因此我们可以考虑在每一个排雷火箭引爆点进行dfs查找下一个地雷的位置，再有下一个地雷的位置递归的查找下下个地雷的位置。找到下一个地雷位置之后，统计该点的地雷个数，最后汇总便是最后答案。

时间复杂度近似为$O(r^2n+m)$

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int M = 999997;
const int Base = 1e9 + 1;

int res;
LL hash1[M]; //hash1用于维护find函数
int hash2[M],hash3[M],book[M]; //hash2:地雷在某点的出现次数 hash3:某点的地雷半径 book:标记该点是否被搜索

//Base进制编码降维
LL get_key(int x,int y)
{
    return (LL)x * Base + y;
}

//手写哈希函数
int find(LL x)
{
    int t = (x % M + M) % M;
    while(hash1[t]!=-1&&hash1[t]!=x)
    {
        t++;
        if(t==M) t=0;
    }
    return t;
}

//判断(x2,y2)是否位于(x1,y1,r1)的范围内
bool judge(int x1,int y1,int x2,int y2,int r)
{
    int d = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
    return d <= r*r;
}

//dfs
void dfs(int x,int y,int r)
{
    for(int i=-r;i<=r;i++)
        for(int j=-r;j<=r;j++)
        {
            int dx = x + i;
            int dy = y + j;
            LL t = get_key(dx,dy);
            if(hash2[find(t)]&&judge(x,y,dx,dy,r)&&!book[find(t)])
            {
                res += hash2[find(t)]; //答案加上该点地雷个数
                book[find(t)] = 1; //标记为已搜索
                dfs(dx,dy,hash3[find(t)]); //搜索下一个点
            }
        }
    return;
}

int main()
{
    int n,m;
    cin>>n>>m;
    memset(hash1,-1,sizeof hash1); //hash1初始化为空
    for(int i=0;i<n;i++)
    {
        int x,y,r;
        cin>>x>>y>>r;
        LL t = get_key(x,y);
        hash1[find(t)] = t; //维护哈希函数
        hash2[find(t)]++; //统计该点地雷数量
        hash3[find(t)] = max(r,hash3[find(t)]); //记录该点地雷半径的最大值
    }
    
    for(int i=0;i<m;i++)
    {
        int x,y,r;
        cin>>x>>y>>r;
        dfs(x,y,r); //从每一个排雷火箭引爆点开始dfs
    }
    cout<<res<<endl;
    return 0;
}