蓝桥杯每日一题20223.9.26
4407. 扫雷 - AcWing题库
题目描述
分析
此题目使用map等都会超时,所以我们可以巧妙的使用哈希模拟散列表,哈希表初始化为-1首先将地雷读入哈希表,找到地雷的坐标在哈希表中对应的下标,如果没有则此地雷的位置第一次出现,将其存入哈希表,di[key]表示哈希数组中key对应的地雷下标,在这些相同位置的地雷中取最大的半径,因为最大的半径炸的范围更多
枚举导弹,如果有地雷,且没有被访问过而且其在爆炸范围之内就可以将其进行bfs
最后遍历每个地雷看是否被标记,被标记就算答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int X = 1e9 + 1, M = 1e6 + 7, N = 5e4 + 10;
struct node
{int x, y, r;
}b[N];
ll h[M], id[M], res, n, m;
bool st[N];
ll get_he(int x, int y)//得到每个坐标的哈希值
{return (ll)x * X + y;
}
int find(int x, int y)//找到坐标被哈希数组储存的下标
{ll he = get_he(x, y);int key = (he % M + M) % M;//映射哈希数组内 while(h[key] != -1 && h[key] != he){key ++;if(key == M)key = 0;}return key;
}
bool check(int x, int y,int r, int xx, int yy)//判断是否在爆炸范围内
{int d = (x - xx) * (x - xx) + (y - yy) * (y - yy);return d <= r * r;
}
void bfs(int pos)
{queue<int>q;q.push(pos);st[pos] = true;while(!q.empty()){int t = q.front();q.pop();int x = b[t].x, y = b[t].y, r= b[t].r;for(int xx = x - r; xx <= x + r; xx ++){for(int yy = y - r; yy <= y + r; yy ++){int key = find(xx, yy);//是地雷,没有访问过,能炸到 if(id[key] && !st[id[key]] && check(x, y, r, xx, yy)){int pos = id[key];st[pos] = true;q.push(pos);}}}}
}
int main()
{cin >> n >> m;memset(h, -1, sizeof h);int x, y, r;for(int i = 1; i <= n; i ++)//地雷 {cin >> x >> y >> r;b[i] = {x, y, r};int key = find(x, y);//找到此地雷对应的下标 if(h[key] == -1)h[key] = get_he(x, y);//如果此下标没有出现过就加入 if(!id[key] || b[id[key]].r < r){id[key] = i;}}for(int i = 1; i <= m; i ++)//排雷导弹{cin >> x >> y >> r;for(int xx = x - r; xx <= x + r; xx ++)//在r的范围内,但可以以圆外的方形区域作为边界 {for(int yy = y - r; yy <= y + r; yy ++){int key = find(xx, yy);if(id[key] && !st[id[key]] && check(x, y, r, xx, yy))bfs(id[key]);}} } for(int i = 1; i <= n; i ++){int key = find(b[i].x, b[i].y);int pos = id[key];if(pos && st[pos])res ++;}cout << res;return 0;
}相关文章:
蓝桥杯每日一题20223.9.26
4407. 扫雷 - AcWing题库 题目描述 分析 此题目使用map等都会超时,所以我们可以巧妙的使用哈希模拟散列表,哈希表初始化为-1首先将地雷读入哈希表,找到地雷的坐标在哈希表中对应的下标,如果没有则此地雷的位置第一次出现&#…...
查看基站后台信息
查看基站后台信息 电脑配置固定ip: 192.168.1.99: 打开“网络和共享中心”,选择更改适配器设置: 右键“本地连接”,选择属性 基站网线直连电脑网口 Telnet 登录基站 打开dos窗口 windows键R”,输入cmd,点确定&…...
关于坐标的旋转变换和坐标系的旋转变换
不管是坐标的旋转变换还是坐标系下的旋转变换,只和旋转的顺时针和逆时针有关。然坐标系间的顺时针和逆时针是根据当前坐标系在目标坐标系下的相对位置确定。 一。逆时针旋转belta角度的公式 二。顺时针旋转belta角度的公式 三。坐标的旋转变换 1.坐标的旋转变换相…...
2023.9.19 关于 数据链路层 和 DNS 协议 基本知识
目录 数据链路层 MTU DNS 协议 补充 DHCP协议 数据链路层 基本概念: 考虑相邻两个节点之间的传输(通过 网线 / 光纤 / 无线 直接相连的两个设备)以太网协议 规定了 数据链路层 和 物理层 的内容 IP地址 与 mac地址 的相互配合 IP地址 描…...
如何保证接口幂等性
简介 接口幂等性就是说用户使用相同的参数请求同一个接口无论是一次还是多次都应该是一样的。不会因为多次的点击产生不同效果。 举个栗子:一个用户在手机APP上提200块钱,然后一不小心点击了两次,那么就应该只提取出200块钱,不应…...
搭建智能桥梁,Amazon CodeWhisperer助您轻松编程
零:前言 随着时间的推移,人工智能技术以惊人的速度向前发展,正掀起着全新的编程范式革命。不仅仅局限于代码生成,智能编程助手等创新应用也进一步提升了开发效率和代码质量,极大地推动着软件开发领域的快速繁荣。 当前…...
数组和指针笔试题解析之【指针】
目录 🍂笔试题1: 🍂笔试题2: 🍂笔试题3: 🍂笔试题4: 🍂笔试题5: 🍂笔试题6: 🍂笔试题7: 🍂笔试题…...
【Linux】之Centos7卸载KVM虚拟化服务
👨🎓博主简介 🏅云计算领域优质创作者 🏅华为云开发者社区专家博主 🏅阿里云开发者社区专家博主 💊交流社区:运维交流社区 欢迎大家的加入! 🐋 希望大家多多支…...
智能电力运维系统:数字化转型在电力行业的关键应用
随着信息技术、人工智能等的飞速发展,数字化改造已成为各行各业的重要发展趋势。在电力行业中,智能电力运维系统是数字化转型的关键应用之一。 力安科技智能电力运维系统是一种集自动化、智能化、云计算、物联网等先进技术于一体的电力运维管理解决方…...
eslint报错:no-empty-source
问题: 提交代码时,eslint校验没有通过,报错 esc[2m183:9esc[22m esc[31mesc[31m✖esc[39m Unexpected empty source esc[2mno-empty-sourceesc[22m 1 problem (esc[31m1 erroresc[39m, esc[33m0 warnings esc[39m) 原因: …...
图论17(Leetcode864.获取所有钥匙的最短路径)
用二进制表示获得的钥匙,假设n钥匙个数 000000000代表没有钥匙,0000000001代表有idx为1的钥匙,0000000011代表有idx1,2的钥匙 (这方法巧妙又复杂.. 代码: class Solution {static int[][] dirs {{-1,0}…...
vue 脚手架 入门 记录
vue 脚手架 入门 记录 以管理员身份运行PowerShell执行:get-ExecutionPolicy,回复Restricted,表示状态是禁止的 3.执行:set-ExecutionPolicy RemoteSigned 4.选择Y 注意:一定要以管理员的身份运行PowerShellÿ…...
汽车租赁系统演示租车小程序H5开发
一款适合汽车租赁业务的程序系统,支持在线支付、一键续租、在线签名。 为了方便用户端方便租车和查看已租车辆的信息和费用,支持上门取车和到店取车两种模式,支持待付款、待取车、待还车、订单管理、已完成、全部订单等订单状态查看和处理功…...
【MySQL】 MySQL 更新数据机制
MySQL 更新数据机制 一、问题描述 假设我们有这样一张表,且包含一条记录: CREATE TABLE mytest ( id int(11) NOT NULL, c1 int(11) DEFAULT NULL, c2 int(11) DEFAULT NULL, c3 int(11) DEFAULT NULL, PRIMARY KEY (id), KEY c1 (c1), KEY c2 (c2) 包…...
批次管理在MES管理系统中有哪些应用
在制造企业中,批次管理是一项至关重要的管理方法,它贯穿于企业的整个生产过程中。特别是在流程制造行业中,如药品、食品等行业,批次管理显得尤为重要。这些行业的产品通常需要进行严格的质量控制和追踪,以便在问题发生…...
python命名规范
一、概述 以前写python代码没有个代码,写出的代码一点也不规范 二、命名规范 2.1类的命名规范 总是使用首字母大写单词串。如MyClass、ClassName。内部类可以使用额外的前导下划线。 2.2函数和方法的命名规范 小写下划线,如method_name。 2.3函数…...
Redis学习笔记--002
Redis的JAVA客户端 文章目录 Redis的JAVA客户端一、Redis的Java客户端的种类二、Jedis2.1、使用步骤2.2、Jedis连接池 三、[SpringDataRedis](https://spring.io/projects/spring-data-redis)3.1、介绍3.2、RedisTemplate3.3、SpringDataRedis使用步骤3.4、SpringDataRedis的序…...
Visual Stdio 2019 win10 64bit下 无法找到 资源编译器DLL,请确认路径是否正确,和无法下载 win10SDK_10.0
上面的2个原因 第一个原因是因为安装时候,漏掉勾选 vistual stdio sdk 和 windows 通用c运行时 其中的一项目 第2个原因是没有安装 sdk...
设计模式:中介者模式(C++实现)
在中介者模式中,中介者对象负责协调多个对象之间的交互,将对象之间的耦合度降低。 #include <iostream> #include <string> #include <vector>class Colleague;// 中介者接口 class Mediator { public:virtual void sendMessage(Coll…...
Python常用函数
最近跑实验,记录一些常用的 Python 函数,便于自己复习和学习,仅用来学习。 1.Python 中的 os.path.join() 参考该文章 深度了解 在 Python 中,处理文件和目录路径是常见的任务。为了简化路径的拼接和操作,Python 提供…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
