自动搬运

查看原文

来自洛谷，原作者为

	zzy0618 VK100.01 P

搬运于2025-08-24 22:42:27，当前版本为作者最后更新于2022-12-27 13:55:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

改掉了之前的错误解法，这下应该没问题了。

思路

有一个性质是 $r\le 10$，也就是一个雷至多引爆 $10^2$ 级别个的位置（不是个数）的雷，而雷的数量级足够我们去暴力寻找这些位置。

将所有炸雷存到一个桶里面，具体的，使用 map 编号，然后存一下在这个位置雷的个数以及这个位置最大的 $r$。对于每个一个排雷火箭使用 dfs 暴力搜，已经被搜过的地方打个标记就行。

这样复杂度是 $O(r^2(n+m)\log n)$ 的，可以通过此题。

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk make_pair
using namespace std;
const int N=1e5+5,M=290023;
int n,m,ans,tot;
int cnt[N],tmp[N],vis[N];
map<pii,int> mp;
void dfs(int x,int y,int r){
	for(int i=x-r;i<=x+r;++i){
		for(int j=y-r;j<=y+r;++j){
			if((i-x)*(i-x)+(j-y)*(j-y)>r*r)continue;
			if(mp.count(mk(i,j))){
				int z=mp[mk(i,j)];
				if(vis[z])continue;
				vis[z]=1;ans+=cnt[z];
				dfs(i,j,tmp[z]);
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1,x,y,z,r;i<=n;++i){
		cin>>x>>y>>r;
		if(mp.count(mk(x,y))){
			int z=mp[mk(x,y)];
			++cnt[z],tmp[z]=max(tmp[z],r);
		}else
			mp[mk(x,y)]=++tot,
			cnt[tot]=1,tmp[tot]=r;
	}for(int i=1,x,y,r,z;i<=m;++i)
		cin>>x>>y>>r,dfs(x,y,r);
	cout<<ans<<'\n';
	return 0;
}