首页 > 其他分享 >[ABC273D] LRUD Instructions 题解

[ABC273D] LRUD Instructions 题解

时间:2024-01-05 21:44:40浏览次数:42  
标签:LRUD temp int 题解 back ny ABC273D sec mpc

[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

相关文章

  • CF1045G AI robots题解
    题目链接:洛谷或者CF本题考虑转化为cdq分治模型对于cdq分治来说,只需要考虑左边对右边的影响,那我们要考虑该怎样设置第一维度的左右对象。很显而易见的是抛开\(q\)限制而言,我们着眼于,如何让双方互相看到的严格条件转化为只需要关注单体看见。考虑什么情况下只需要一方看到......
  • nested exception is java.lang.IllegalArgumentException异常问题解决
    项目启动报错如下:nestedexceptionisjava.lang.IllegalArgumentException:Couldnotresolveplaceholder'xxx'invalue"${xxx}"问题解决比较简单,只说我所遇到的情况,原因就是字母拼写问题仔细看还是能看到大写的K和小写的k有一些细微的区别,将nacos中的k和代码中修改一致后启......
  • 奇迹服务端问题解答
    1.怎么修改IIS的连接限制10个啊暂时好像没有完善的修改软件,有是有,但是我试了几次都失败,就不推荐了2.怎么修改游戏中商店出售的物品啊DMuServerDataShop1.txt~Shop11.txt3.Terrain1.Att~Terrain35.Att这些有什么用啊这个是服务端地图...4.服务端的怪物太吊了怎么修改它们LS点啊DM......
  • [ABC271E] Subsequence Path 题解
    [ABC271E]SubsequencePath题解思路解析很好的一道题,很有迷惑性,表面上是一道图论实际上是dp,定义\(f_{i}\)为从\(1\)到\(i\)的最短“好路”。先把每条边对应的起点,终点和边权记录下来,然后输入每个\(e\),由于是子序列顺序不会改变,因此可以顺序进行操作。对于每一个\(e......
  • P2726 [SHOI2005] 树的双中心 题解
    Description\(n\leq5\times10^4\),树的深度\(\leq100\)。Solution对于每个\(x,y\),满足\(d(v,x)\leqd(v,y)\)或者\(d(v,x)\geqd(v,y)\)的点一定构成一个子树,所以可以枚举这个子树的根,然后对两边分别求重心可以得到答案。但是直接暴力求是\(O(n^2)\)的,过不了。注......
  • CF763E Timofey and our friends animals题解
    题目链接:CF或者洛谷简单来说就是求\([l,r]\)这些点都存在的情况下,连通块的数量,看到七秒时限,而且每个点相连的边数很少,可以想到离线下来使用莫队类的算法解决连通块问题,一般可以考虑使用并查集解决。对于并查集来说,它的增加是非常简单的,但删除是困难的,可持久化并查集时空常数......
  • TinyMCE富文本编辑器粘贴图片自动上传问题解决
    TinyMCE编辑器支持粘贴图片,但是自动会将图片转换成base64编码,这样将内容提交到后台,数据会很大。  图|TinyMCE本文内容配置TinyMCE(版本:5.10.0)向编辑器中粘贴图片自动上传到后台,以下为配置代码:tinymce.init({selector:'#textarea',plugins:'previewautolinkdire......
  • 2023NCTFcheck题解-关于可视化shellcode以及AE64真香
    以后我会尽量少用图片,因为我经常在翻别人博客时发现图片加载不出来,很烦。看看checksec再看看IDAint__cdeclmain(intargc,constchar**argv,constchar**envp){__int64v3;//rbx__int64v4;//rbx__int64v5;//rbxunsigned__int64v7;//[rsp+8h][rbp-2......
  • P9753 [CSP-S 2023] 消消乐 题解
    这里是被说烂了的随机化线性做法。相信大家都已经做过QOJ6504,因此我们考虑采用类似的办法通过此题。我们对每个字符随机一个\(k\timesk\)的矩阵,并求出其矩阵的逆。然后,我们在偶数位放原矩阵,在奇数位放逆矩阵,这样,一段区间合法当且仅当这段区间的矩阵积为单位矩阵\(I\),原因......
  • CSP-S 题解
    非考场上想出来的会标星号。T1密码锁鲜花:我看到这道题的时候满脑子想的都是春测的lock。考虑到只有五个拨圈,每个拨圈只有\(10\)个状态,\(n\le8\),那么直接暴力枚举每个状态即可。考场代码://15:00//15:24.#include<bits/stdc++.h>usingnamespacestd;constin......