【洛谷 P8695】[蓝桥杯 2019 国 AC] 轨道炮 题解(映射+模拟+暴力枚举+桶排序)
[蓝桥杯 2019 国 AC] 轨道炮
题目描述
小明在玩一款战争游戏。地图上一共有 N N N 个敌方单位,可以看作 2D 平面上的点。其中第 i i i 个单位在 0 0 0 时刻的位置是 ( X i , Y i ) (X_i, Y_i) (Xi,Yi),方向是 D i D_i Di (上下左右之一, 用 U/D/L/R 表示),速度是 V i V_i Vi。小明的武器是轨道炮,只能使用一次,不过杀伤力巨大。小明可以选择在某个非负整数时刻释放轨道炮,轨道炮一次可以消灭在一条直线 (平行于坐标轴) 上的所有敌方单位。请你计算小明最多能消灭多少敌方单位。
输入格式
输入第一行包含一个整数 N N N。
以下 N N N 行每行包含 3 3 3 个整数 X i X_i Xi, Y i Y_i Yi, V i V_i Vi,以及一个大写字符 D i D_i Di。
输出格式
输出一个整数代表答案。
样例 #1
样例输入 #1
4
0 0 1 R
0 10 1 R
10 10 2 D
2 3 2 L
样例输出 #1
3
提示
对于所有评测用例, 1 ≤ N ≤ 1000 1 \le N \le 1000 1≤N≤1000, − 1 0 6 ≤ X i , Y i ≤ 1 0 6 -10^6 \le X_i, Y_i \le 10^6 −106≤Xi,Yi≤106, 0 ≤ V i ≤ 1 0 6 0 \le V_i \le 10^6 0≤Vi≤106。
蓝桥杯 2019 年国赛 A 组 H 题(C 组 J 题)
思路
首先定义一些常量、变量和数据结构。其中,N 是单位的最大数量,T 是模拟的最大时间。定义了一个 Unit 结构体,表示单位,包括单位的位置 (x, y),速度 v 和方向 d。定义了两个哈希表 cntX 和 cntY,用于记录每个坐标上的单位数量。定义了一个哈希表 dir,用于记录每个方向的位移。
接着从输入中读取单位数量 n 和每个单位的信息,包括位置、速度和方向。然后进行 T 轮模拟,每轮模拟中,首先清空 cntX 和 cntY,然后对每个单位进行移动,并更新 cntX 和 cntY。
cntX 和 cntY 可以看作是桶,键是坐标,值是该坐标上的单位数量。对于每个单位,根据其位置更新 cntX 和 cntY,将单位分布到桶中。然后找出 cntX 和 cntY 中的最大值,更新最大消灭单位数量 ans。
最后输出 ans。
AC代码
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;const int N = 2e6 + 7;
const int T = 4e2 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;int n;
map<int, ll> cntX, cntY;
map<char, pair<int, int>> dir;struct Unit {int x, y;int v;char d;
} unit[N];void init() {dir.clear();dir['L'] = {-1, 0};dir['R'] = {1, 0};dir['U'] = {0, 1};dir['D'] = {0, -1};
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);init();cin >> n;for (int i = 1; i <= n; i++) {int x, y, v;char d;cin >> x >> y >> v >> d;unit[i] = {x, y, v, d};}ll ans = 0;for (int t = 0; t <= T; t++) {cntX.clear();cntY.clear();for (int i = 1; i <= n; i++) {auto u = unit[i];cntX[u.x]++;cntY[u.y]++;}ll maxi = 0;for (const auto i : cntX) {maxi = max(maxi, i.second);}for (const auto i : cntY) {maxi = max(maxi, i.second);}// cout << maxi << endl;ans = max(ans, maxi);for (int i = 1; i <= n; i++) {int v = unit[i].v;auto dd = dir[unit[i].d];unit[i].x += v * dd.first;unit[i].y += v * dd.second;}}cout << ans << "\n";return 0;
}

相关文章:
【洛谷 P8695】[蓝桥杯 2019 国 AC] 轨道炮 题解(映射+模拟+暴力枚举+桶排序)
[蓝桥杯 2019 国 AC] 轨道炮 题目描述 小明在玩一款战争游戏。地图上一共有 N N N 个敌方单位,可以看作 2D 平面上的点。其中第 i i i 个单位在 0 0 0 时刻的位置是 ( X i , Y i ) (X_i, Y_i) (Xi,Yi),方向是 D i D_i Di (上下左右之一, 用…...
高阶DS---AVL树详解(每步配图)
目录 前言: AVL树的概念: AVL树节点的定义: AVL树的插入(重点) AVL树的旋转: (1)新节点插入较高左子树的左侧---右单旋 (2)新节点插入较高右子树的右侧---左单旋 …...
c++前言
目录 1. 什么是 C 2. C 发展史 3. C 的重要性 4. 如何学习 C 5. 关于本门课程 1. 什么是C C语言是结构化和模块化的语言,适合处理较小规模的程序。对于复杂的问题,规模较大的 程序,需要高度的抽象和建模时, C 语言则不合适…...
2024年泰迪杯数据挖掘B题详细思路代码文章教程
目前b题已全部更新包含详细的代码模型和文章,本文也给出了结果展示和使用模型说明。 同时文章最下方包含详细的视频教学获取方式,手把手保姆级,模型高精度,结果有保障! 分析: 本题待解决问题 目标&#…...
练习 21 Web [GXYCTF2019]BabySQli
SQL联合查询,注意有源码看源码,Base64以及32的区别,MD5碰撞 打开后有登录框,先随意登录尝试 只有输入admin才是返回wrong pass! 其他返回wrong user 所以用户名字段一定要输入admin 养成好习惯,先查看源码…...
【并发编程】CountDownLatch
📝个人主页:五敷有你 🔥系列专栏:并发编程 ⛺️稳中求进,晒太阳 CountDownLatch 概念 CountDownLatch可以使一个获多个线程等待其他线程各自执行完毕后再执行。 CountDownLatch 定义了一个计数器,…...
2024-HW --->SSRF
这不是马上准备就要护网了嘛,如火如荼的报名ing!!!那么小编就来查缺补漏一下以前的web漏洞,也顺便去收录一波poc!!!! 今天讲的主人公呢就是SSRF,以前学的时候…...
该主机与 Cloudera Manager Server 失去联系的时间过长。 该主机未与 Host Monitor 建立联系
该主机与 Cloudera Manager Server 失去联系的时间过长。 该主机未与 Host Monitor 建立联系 这个去集群主机cm界面上看会出现这个错误 排查思路: 一般比较常见的原因可能是出问题的主机和集群主节点的时间对应不上了。还有就是cm agent服务出现问题了 去该主机的…...
【BUG】No module named ‘dnf‘
报错内容: 类型一 # git clone https://github.com/pytorch/vision.git Cloning into vision... /usr/libexec/git-core/git-remote-https: symbol lookup error: /usr/lib64/libldap.so.2: undefined symbol: EVP_md2, version OPENSSL_1_1_0类型二 # yum reins…...
Ubuntu pycharm配置Conda环境
参考博客:https://blog.csdn.net/qq_40726937/article/details/105323965 https://juejin.cn/post/7229543139950051388 Ubuntu20.04中搭建虚拟环境并且用pycharm调用Ubuntu中的虚拟环境。_ubuntu pycharm的虚拟环境选哪个-CSDN博客...
工作体验记录
文章目录 如何提高说话能力?如何提高行动力?如何完成一个任务产出成果?如何寻找突破点提高解决问题的效率?如何成为技术领导?参考资料 如何提高说话能力? 三思而后说,想清楚问题描述,抓住重点…...
YOLO火灾烟雾检测数据集:20000多张,yolo标注完整
YOLO火灾烟雾检测数据集:一共20859张图像,yolo标注完整,部分图像应用增强 适用于CV项目,毕设,科研,实验等 需要此数据集或其他任何数据集请私信...
基于Spring Boot的餐厅点餐系统
基于Spring Boot的餐厅点餐系统 开发语言:Java框架:springbootJDK版本:JDK1.8数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:Maven3.3.9 部分系统展示 管理员登录界面 用户注册登录界面 …...
tkinter控件教程使用说明(三)
这篇tkinter控件使用教程是最后一 一、TreeView 属性/事件描述代码实例columns列名,用于设置树形视图的列tree["columns"] ("姓名", "年龄", "性别")column列的属性,包括列名、宽度等tree.column("姓名…...
Electron 打包自定义NSIS脚本为安装向导增加自定义页面增加输入框
Electron 打包工具有很多,如Electron-build、 Electron Forge 等,这里使用Electron-build,而Electron-build使用了nsis组件来创建安装向导,默认情况nsis安装向导不能自定义安装向导界面,但是nsis提供了nsis脚本可以扩展…...
Idea2023创建Servlet项目
① Java EE 只是一个抽象的规范,具体实现称为应用服务器。 ② Java EE 只需要两个包 jsp-api.jar 和 servlet-api.jar,而这两个包是没有官方版本的。也就是说,Java 没有提供这两个包,只提供了一个规范。那么这两个包是谁提供的…...
Day57:WEB攻防-SSRF服务端请求Gopher伪协议无回显利用黑白盒挖掘业务功能点
目录 SSRF-原理&挖掘&利用&修复 SSRF无回显解决办法 SSRF漏洞挖掘 SSRF协议利用 http:// (常用) file:/// (常用) dict:// (常用) sftp:// ldap:// tftp:// gopher:// (…...
【Qt】使用Qt实现Web服务器(十):前端基础
1、简述 本人对HTML元素不熟悉,利用QtWebApp加载静态页面来熟悉下HTML元素。 2、测试代码 # a)main中创建 HttpListener new HttpListener(listenerSettings,new RequestMapper(&app),&app);#...
使用vuepress搭建个人的博客(一):基础构建
前言 vuepress是一个构建静态资源网站的库 地址:VuePress 一般来说,这个框架非常适合构建个人技术博客,你只需要把自己写好的markdown文档准备好,完成对应的配置就可以了 搭建 初始化和引入 创建文件夹press-blog npm初始化 npm init 引入包 npm install -D vuepress…...
ArcGIS Pro导出布局时去除在线地图水印
目录 一、背景 二、解决方法 一、背景 在ArcGIS Pro中经常会用到软件自带的在线地图,但是在导出布局时,图片右下方会自带地图的水印 二、解决方法 解决方法:添加动态文本--服务图层制作者名单,然后在布局中选定位置添加 在状…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
