[ABC273D] LRUD Instructions 题解
很好的一道大模拟,使我爆 \(0\)。
思路解析
大模拟,我们只需要用一个 \(x,y\) 表示我们当前的位置,而对于每一个移动,我们就判断在当前移动方向上离当前点最近的点,若该点在当前行进路线上,则把当前位置设为该点前面的一个。
其中判断在当前移动方向上离当前点最近的点可以使用离散化,然后使用二分法查找第一个大于当前点的障碍物,而若是朝负方向移动,则可以修改 lower_bound
里的迭代器起终点和 cmp
函数,这样就可以用 lower_bound
实现反向二分。
PS:考试时能用 vector
就千万不要用 set
!!!常数奇大无比!! 挂分记录
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fir first
#define sec second
int h, w, n;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int sx, sy;
map<int, vector<int> > mph, mpl;
map<char, int> mpc;
int q;
void init() {
mpc['U'] = 0;
mpc['D'] = 1;
mpc['L'] = 2;
mpc['R'] = 3;
}
signed main() {
init();
cin >> h >> w >> sx >> sy;
cin >> n;
for(int i = 1, r, c; i <= n; i++) {
cin >> r >> c;
mph[r].push_back(c);
mpl[c].push_back(r);
}
for(auto &it : mph) {
it.sec.push_back(0);
it.sec.push_back(2e9);
sort(it.sec.begin(), it.sec.end());
}
for(auto &it : mpl) {
it.sec.push_back(0);
it.sec.push_back(2e9);
sort(it.sec.begin(), it.sec.end());
}
cin >> q;
int x = sx, y = sy;
while(q--) {
char ch;
int l;
cin >> ch >> l;
int d = mpc[ch];
int nx = x + dx[d] * l;
nx = max(1ll, nx);
nx = min(nx, h);
int ny = y + dy[d] * l;
ny = max(1ll, ny);
ny = min(ny, w);
if(d == 0) {
if(!mpl[ny].empty()) {
int temp = *lower_bound(mpl[ny].rbegin(), mpl[ny].rend(), x, [](int xx, int yy) { //lambda表达式
return xx > yy;
});
if(temp >= nx && temp <= x) {
x = temp + 1;
}
else {
x = nx;
}
}
else {
x = nx;
}
}
else if(d == 1) {
if(!mpl[ny].empty()) {
int temp = *lower_bound(mpl[ny].begin(), mpl[ny].end(), x);
if(temp >= x && temp <= nx) {
x = temp - 1;
}
else {
x = nx;
}
}
else {
x = nx;
}
}
else if(d == 2) {
if(!mph[nx].empty()) {
int temp = *lower_bound(mph[nx].rbegin(), mph[nx].rend(), y, [](int xx, int yy) {
return xx > yy;
});
if(temp >= ny && temp <= y) {
y = temp + 1;
}
else {
y = ny;
}
}
else {
y = ny;
}
}
else if(d == 3) {
if(!mph[nx].empty()) {
int temp = *lower_bound(mph[nx].begin(), mph[nx].end(), y);
if(temp >= y && temp <= ny) {
y = temp - 1;
}
else {
y = ny;
}
}
else {
y = ny;
}
}
cout << x << " " << y << "\n";
}
return 0;
}
标签:LRUD,temp,int,题解,back,ny,ABC273D,sec,mpc
From: https://www.cnblogs.com/2020luke/p/17948154