[蓝桥杯 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;
}
