草庐IT

蓝桥杯 - 试题 H: 扫雷(思维)

Frozen_Guardian 2023-04-03 原文


题目大意：给出 n n n 个地雷和 m m m 个炸弹，都以 ( x , y , r ) (x,y,r) (x,y,r) 的形式给出，意义分别如下：

  1. 对于每个地雷，位于点 ( x , y ) (x,y) (x,y)，爆炸后会波及半径为 r r r 的圆形区域
  2. 对于每个炸弹，会在点 ( x , y ) (x,y) (x,y) 爆炸，爆炸后会引爆半径为 r r r 的圆形区域内的地雷，随后地雷会 “连锁反应” 的爆炸

问使用过 m m m 个炸弹后，一共可以引爆多少个地雷

题目分析：（赛时读错题了，怪不得当时算复杂度的时候能多算一个 l o g log log 出来）

最初的思想肯定是，先让可以“连锁反应”的地雷建立关系，这样引爆其中的一个地雷后，由“连锁反应”所引爆的地雷就不会被重复判断了，可以做到每个地雷至多被遍历一次。

需要发现一个很重要的细节就是，地雷引爆的关系是单向的，如果地雷 A 可以引爆地雷 B ，不一定能得出地雷 B 可以引爆地雷 A

所以整个“连锁反应”是一个有向图，不能使用并查集处理连通性。在建出有向图后索性直接用 dfs 暴力遍历即可，因为上面的思路已经保证了每个地雷至多遍历一次，所以 dfs 的复杂度是线性的

现在的问题转换为该如何快速建边，观察数据范围不难发现半径 r r r 给的特别小，所以可以将圆心用 map 映射一下，然后每次只需要遍历圆内的点尝试建边就好了

时间复杂度： O ( n ∗ 320 ∗ l o g n ) O(n*320*logn) O(n∗320∗logn)，这里的 320 320 320 代表的是半径为 10 10 10 的圆内的点数

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+100;
struct Point {
	int x,y,r;
	void input() {
		scanf("%d%d%d",&x,&y,&r);
	}
}p1[N],p2[N];
bool vis[N];
map<pair<int,int>,vector<int>>mp;
vector<int>node[N];
int dfs(int u) {
	if(vis[u]) {
		return 0;
	}
	vis[u]=true;
	int ans=1;
	for(auto v:node[u]) {
		ans+=dfs(v);
	}
	return ans;
}
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		p1[i].input();
		mp[{p1[i].x,p1[i].y}].push_back(i);
	}
	for(int i=1;i<=m;i++) {
		p2[i].input();
	}
	for(int i=1;i<=n;i++) {
		for(int dx=-10;dx<=10;dx++) {
			for(int dy=-10;dy<=10;dy++) {
				LL x=p1[i].x,y=p1[i].y;
				LL xx=x+dx,yy=y+dy;
				LL r=p1[i].r;
				if((x-xx)*(x-xx)+(y-yy)*(y-yy)<=r*r) {
					for(auto j:mp[{xx,yy}]) {
						node[i].push_back(j);
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++) {
		for(int dx=-10;dx<=10;dx++) {
			for(int dy=-10;dy<=10;dy++) {
				LL x=p2[i].x,y=p2[i].y;
				LL xx=x+dx,yy=y+dy;
				LL r=p2[i].r;
				if((x-xx)*(x-xx)+(y-yy)*(y-yy)<=r*r) {
					for(auto j:mp[{xx,yy}]) {
						ans+=dfs(j);
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
蓝桥试题spanclasstoken其他

有关蓝桥杯 - 试题 H: 扫雷(思维)的更多相关文章

  1. Hive SQL 五大经典面试题 - 2

    目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类

  2. 蓝桥杯备赛（二） - 2

    目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言：  在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC  已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析  这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy

  3. 常见网络安全产品汇总（私信发送思维导图） - 2

    安全产品安全网关类防火墙Firewall防火墙防火墙主要用于边界安全防护的权限控制和安全域的划分。防火墙•信息安全的防护系统，依照特定的规则，允许或是限制传输的数据通过。防火墙是一个由软件和硬件设备组合而成，在内外网之间、专网与公网之间的界面上构成的保护屏障。下一代防火墙•下一代防火墙，NextGenerationFirewall，简称NGFirewall，是一款可以全面应对应用层威胁的高性能防火墙，提供网络层应用层一体化安全防护。生产厂家•联想网御、CheckPoint、深信服、网康、天融信、华为、H3C等防火墙部署部署于内、外网编辑额，用于权限访问控制和安全域划分。UTM统一威胁管理（Un

  4. 蓝桥杯C/C++VIP试题每日一练之报时助手 - 2

    ?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5

  5. 十四届蓝桥青少组模拟赛Python-20221108 - 2

    十四届蓝桥青少组模拟赛Python-20221108T1.二进制位数十进制整数2在十进制中是1位数，在二进制中对应10，是2位数。十进制整数22在十进制中是2位数，在二进制中对应10110，是5位数。请问十进制整数2022在二进制中是几位数？print(len(bin(2022))-2)#运行结果：11T2.晨跑小蓝每周六、周日都晨跑，每月的1、11、21、31日也晨跑。其它时间不晨跑。已知2022年1月1日是周六，请问小蓝整个2022年晨跑多少天？#样例代码1ls=[0,31,28,31,30,31,30,31,31,30,31,30,31]ans=0k=6foriinrange(1,13)

  6. 华为OD机试 -旋转骰子（Python） | 机试题算法思路 【2023】 - 2

    最近更新的博客华为OD机试-卡片组成的最大数字（Python）|机试题算法思路华为OD机试-网上商城优惠活动（一）（Python）|机试题算法思路华为OD机试-统计匹配的二元组个数（Python）|机试题算法思路华为OD机试-找到它（Python）|机试题算法思路华为OD机试-九宫格按键输入（Python）|机试算法备考思路华为OD机试-身高排序（Python）|备考思路使用说明参加华为od机试，一定要注意不要完全背诵代码，需要理解之后模仿写出，通过率才会高。华为OD清单查看地址：blog.csdn.net/hihell/catego

  7. 蓝桥杯 stm32 MCP4017 - 2

    本文代码使用HAL库。文章目录前言一、MCP4017的重要特性二、MCP4017计算RBW阻值三、MCP4017地址四、MCP4017读写函数五、CubeMX创建工程（利用ADC测量MCP4017电压）、对应代码：总结前言一、MCP4017的重要特性蓝桥杯板子上的是MCP4017T-104ELT，如图1。MCP4017是一个可编程电阻，通过写入的数值可以改变电阻的大小。重点在于6引脚（W），5引脚（B&#

  8. [蓝桥杯单片机]学习笔记——串口通信的基本原理与应用 - 2

    目录一、原理部分1、什么是串行通信（1）并行通信与串行通信（2）串行通信的制式（3）串行通信的主要方式  2、配置串口（1）SCON和PCON：串行口1的控制寄存器（2）SBUF：串行口数据缓冲寄存器 （3）AUXR：辅助寄存器​编辑（4）ES、PS：与串行口1中断相关的寄存器（5）波特率设置  3、串口框架编写二、程序案例一、原理部分1、什么是串行通信（1）并行通信与串行通信微控制器与外部设备的数据通信，根据连线结构和传送方式的不同，可以分为两种：并行通信和串行通信。并行通信：数据的各位同时发送与接收，每个数据位使用一条导线，这种方式传输快，但是需要多条导线进行信号传输。串行通信：数据一位一

  9. 考勤刷卡 最大和 简单 蓝桥杯省赛 2022 - 2

    问题描述小蓝负责一个公司的考勤系统,他每天都需要根据员工刷卡的情况来确定每个员工是否到岗。当员工刷卡时,会在后台留下一条记录,包括刷卡的时间和员工编号,只要在一天中员工刷过一次卡,就认为他到岗了。现在小蓝导出了一天中所有员工的刷卡记录,请将所有到岗员工的员工编号列出。输入格式输入的第一行包含一个正整数n,表示一天中所有员工的刷卡记录的条数。接下来n行,每行包含一条刷卡记录,每条刷卡记录的格式为:HH:MM:SSID其中HH:MM:SS表示刷卡时间,HH为一个0到23之间的两位十进制整数(可能含前导0)表示时,MM为一个0到59之间的两位十进制整数(可能含前导0)表示分,SS为一个0到59之间的

  10. ruby - 配置思维 sphinx 和飞行 sphinx 时出错 - 2

    我在Heroku上运行了Rails3应用程序。我在我的应用程序中使用ThinkingSphinx搜索引擎。为了让它与Heroku一起工作，我按照Heroku文档中的建议向我的gemfile添加了一个flying-sphinxgem。这是我的gemfile中的内容gem'thinking-sphinx','2.0.11'gem'flying-sphinx','0.7.0'按照此处提到的步骤https://devcenter.heroku.com/articles/flying_sphinx,添加flying-sphinx插件后(Herokuaddons:addflying_sphinx:

随机推荐