海南建设工程信息网站,html免费模板下载,网站后期维护合同,创意做网站公司[蓝桥杯 2019 国 AC] 轨道炮
题目描述
小明在玩一款战争游戏。地图上一共有 N N N 个敌方单位#xff0c;可以看作 2D 平面上的点。其中第 i i i 个单位在 0 0 0 时刻的位置是 ( X i , Y i ) (X_i, Y_i) (Xi,Yi)#xff0c;方向是 D i D_i Di (上下左右之一, 用…[蓝桥杯 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;
mapint, ll cntX, cntY;
mapchar, pairint, 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;
}
