【洛谷 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 1N1000 − 1 0 6 ≤ X i , Y i ≤ 1 0 6 -10^6 \le X_i, Y_i \le 10^6 106Xi,Yi106 0 ≤ V i ≤ 1 0 6 0 \le V_i \le 10^6 0Vi106

蓝桥杯 2019 年国赛 A 组 H 题(C 组 J 题)


思路

首先定义一些常量、变量和数据结构。其中,N 是单位的最大数量,T 是模拟的最大时间。定义了一个 Unit 结构体,表示单位,包括单位的位置 (x, y),速度 v 和方向 d。定义了两个哈希表 cntXcntY,用于记录每个坐标上的单位数量。定义了一个哈希表 dir,用于记录每个方向的位移。

接着从输入中读取单位数量 n 和每个单位的信息,包括位置、速度和方向。然后进行 T 轮模拟,每轮模拟中,首先清空 cntXcntY,然后对每个单位进行移动,并更新 cntXcntY

cntXcntY 可以看作是桶,键是坐标,值是该坐标上的单位数量。对于每个单位,根据其位置更新 cntXcntY,将单位分布到桶中。然后找出 cntXcntY 中的最大值,更新最大消灭单位数量 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;
}


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515510.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

kubadm部署kubernetes

什么是kubernetes Kubernetes是一款应用于集群的&#xff0c;容器自动部署、扩展和管理的开源平台&#xff0c;提供了一种以容器为中心的基础架构。利用kubernetes&#xff0c;你可以快速高效地响应客户如下请求&#xff1a; 应用程序的动态、精准部署应用程序的动态扩展无缝推…

【机器学习】K-近邻算法(KNN)介绍、应用及文本分类实现

一、引言 1.1 K-近邻算法&#xff08;KNN&#xff09;的基本概念 K-近邻算法&#xff08;K-Nearest Neighbors&#xff0c;简称KNN&#xff09;是一种基于实例的学习算法&#xff0c;它利用训练数据集中与待分类样本最相似的K个样本的类别来判断待分类样本所属的类别。KNN算法…

2024福建三支一扶报名流程,超全超详细!

2024年福建三支一扶报名已经开始&#xff0c;请注意时间&#xff01; ⚠2024年福建省省级“三支一扶”计划招募岗位1070个 报名时间&#xff1a;4月1日8:00至4月17日17:00 审查考核&#xff1a;4月18日至5月10日 确定派遣人员&#xff1a;5月11日至5月31日 报名入口&#xff1…

数据质量决定大模型能力,景联文科技提供高质量大模型数据

随着大模型的深入发展&#xff0c;各类资源要素的配置状态已悄然变化。其中&#xff0c;数据的价值已被提升到一个新高度。 大模型往往拥有庞大的参数和复杂的网络结构&#xff0c;需要大量的数据来学习和优化。数据的质量和数量直接决定了模型的训练效果。若数据不足或质量不佳…

【JavaScript 漫游】【051】Set 和 Map 数据结构

文章简介 本篇文章为【JavaScript 漫游】专栏的第 051 篇文章&#xff0c;记录了 ES6 规范新增的 Set 和 Map 数据结构的相关知识点。 SetWeakSetMapWeakMap Set 基本用法 类似于数组&#xff0c;但是成员的值都是唯一的&#xff0c;没有重复的值。 Set 本身是一个构造函…

IT外包行业未来发展趋势

随着企业对高可用性系统和分布式系统需求的增加&#xff0c;IT人才外包行业迎来了前所未有的发展机遇。未来几年&#xff0c; IT外包行业将呈现出一系列发展趋势 首先&#xff0c;IT外包人才队伍将不断壮大。随着企业对人效的需求日益增长&#xff0c;以及为规避用工风险和降低…

StarRocks实战——携程火车票指标平台建设

目录 前言 一、早期OLAP架构与痛点 二、指标平台重构整体设计 2.1 指标查询过程 2.1.1 明细类子查询 2.1.2 汇总类子查询 2.1.3 “缓存” 2.2 数据同步 三、Starrocks使用经验分享 3.1 建表经验 3.2 数据查询 3.3 函数问题 四、查询性能大幅提升 五、 后续优化方…

LeetCode575——分糖果

题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 这道题比较简单&#xff0c;但我还是花费了将近四个小时的时间去解答&#xff0c;AC的那一刻&#xff0c;终于全身舒畅&#xff0c;这道题的思路就是先求出糖果的种数&#xff0c;然后我们从题中可以得出&#x…

PMP备考需要多长时间?

PMP备考需要多久&#xff1f;50天就能顺利学完 PMP考试备考时间需要看自己的工作安排了&#xff0c;学习周期要恰到好处&#xff0c;太长的话可能导致边学边忘&#xff0c;根本来不及总结冲刺&#xff1b;太短的话又会造成学习内容掌握不稳定&#xff0c;导致考试的时候发挥失…

JavaScript(一)基础

文章目录 一、JS介绍JavaScript是什么JavaScript书写位置JavaScript的注释输入输出语法字面量 二、变量变量是什么变量基本使用变量的本质变量命名规则与规范变量拓展-数组var与let的区别 三、常量四、数据类型数据类型检测数据类型数据类型转换隐式转换显式转换 简单运算符断点…

3.冒泡排序

冒泡排序 基本思想&#xff1a;每次比较两个相邻的元素 如果它们的顺序错误就把它们交换过来 重点&#xff1a;交换 时间复杂度为&#xff1a;O(n^2)&#xff08;平均情况、最坏情况&#xff09; 最优情况&#xff1a;输入的数组已经是完全有序的时候 冒泡排序只需要进行一…

day11 java不同对象的关联与内存分析 JavaBean用途及讲解 import导入包

不同对象的关联与内存分析 内存图&#xff1a; 对象的属性是另一个对象时&#xff0c;在堆内存内该属性对应的值是另一个对象的首地址&#xff08;指向另一个堆内存内另一个对象&#xff09;&#xff0c;两对象建立了联系&#xff0c;可以根据箭头间接调用。 JavaBean…

基于SpringBoot + Vue实现的员工绩效考核管理系统设计与实现+毕业论文+PPT+任务书+搭建视频

介绍 系统包含员工和管理员两个角色 管理员&#xff1a; 部门管理&#xff1a;负责创建、修改和删除部门&#xff0c;以及为部门设置权限和角色。 岗位管理&#xff1a;定义和管理岗位信息&#xff0c;包括添加、修改和删除岗位&#xff0c;以及设置岗位的职责和要求 员工…

一、企业级架构之LNMP

一、LNMP 概述 1、LNMP之间的关系&#xff1a; LNMP Linux Nginx MySQL PHP 2、配置LNMP服务器&#xff1a; (1) 克隆一台centos7虚拟机&#xff0c;修改 IP 地址 和 UUID 编号。 IP 为 10.1.1.10&#xff0c;UUID 修改后三位。 (2) 设置主机名称&#xff0c;绑定IP地…

计算机组成原理-10-控制单元的设计

10. 控制单元的设计 文章目录 10. 控制单元的设计10.1 组合逻辑设计10.1.1 CU外特性10.1.2 微操作的节拍安排10.1.3 组合逻辑设计步骤 10.2 微程序设计10.2.1 微程序设计思想10.2.2 微指令格式10.2.3 毫微程序设计10.2.4 微程序设计举例 完结撒花 本笔记参考哈工大刘宏伟老师的…

最新社交相亲系统源码PHP

最新社交相亲系统源码PHP 安装环境&#xff1a; php7.2 mysql 5.7 框架&#xff1a; 后端thinkphp6 前端&#xff1a;jquery layui PC 移动端响应式 线上案例&#xff1a;https://cjr.oemsun.com/ 主要页面及功能预览 首页 相亲资料详情页 红娘跟进记录 海报、一键复制分…

Cisco ACI Simulator 6.0(5h) - ACI 模拟器

Cisco ACI Simulator 6.0(5h) - ACI 模拟器 Application Centric Infrastructure (ACI) Simulator Software 请访问原文链接&#xff1a;https://sysin.org/blog/cisco-acisim-6/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sysin.o…

【核弹级安全事件】XZ Utils库中发现秘密后门,影响主要Linux发行版,软件供应链安全大事件

Red Hat 发布了一份“紧急安全警报”&#xff0c;警告称两款流行的数据压缩库XZ Utils&#xff08;先前称为LZMA Utils&#xff09;的两个版本已被植入恶意代码后门&#xff0c;这些代码旨在允许未授权的远程访问。 此次软件供应链攻击被追踪为CVE-2024-3094&#xff0c;其CVS…

卡奥斯工业互联网平台分析

一、 背景 卡奥斯是海尔推出的具有中国自主知识产权、全球首家引入用户全流程参与体验的工业互联网平台。其核心是大规模定制模式&#xff0c;通过持续与用户交互&#xff0c;将硬件体验变为场景体验&#xff0c;将用户由被动的购买者变为参与者、创造者&#xff0c;将企业由原…

Vue3配置router路由步骤

Vue3配置router路由步骤 首先创建一个vue3的项目 先检查一下router的版本&#xff0c;可以在pakage.json里面查看&#xff0c;也可以你直接在终端输入 npm list vue-router如果版本比较低的话&#xff0c;先升级一下 vue3的话&#xff0c;用以下命令 npm install vue-route…