自动搬运

查看原文

来自洛谷，原作者为

	LiuenzeGESP 这个家伙不懒，但是一个蒟蒻

搬运于2025-08-24 23:06:49，当前版本为作者最后更新于2024-12-10 20:57:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

本题仅需模拟即可，不需要二叉树的数据结构。第 $2$ 或第 $3$ 种移动后节点的编号变化在题目中已经写得很清楚了。

接下来考虑第 $1$ 种移动后的节点编号变化，我们可以使用倒推法。

假设当前所在节点编号为 $s$，它的父节点编号为 $i$。如果 $s$ 是 $i$ 的左儿子，根据题意可得 $2 \times i =s$，求得 $i=\frac{s}{2}$。

如果 $s$ 是 $i$ 的右儿子，可得 $2 \times i + 1 = s$，求得 $i=\frac{s-1}{2}$（因为此时 $s$ 一定是一个奇数，所以这个式子的值其实就相当于 $\lfloor \frac{s}{2} \rfloor$）。

综上所述，我们只需要用 $s$ 整除以 $2$ 就可以求出其父节点的编号。

还有一点：题目只说最后所处的节点编号不超过 $10^{12}$，没说经过的节点编号不超过 $10^{12}$，如果直接写就会喜提 $40$ 分的成绩（因为会爆 long long）。这是教训。

解决方案：一旦编号超过 $10^{12}$，就暂时不进行第 $2$ 或第 $3$ 种移动。记下来，等到进行第 $1$ 种移动时抵消掉。

最后按题意模拟即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long//不开long long见祖宗
int n,s,t;
int inf=1e12;
string str;
signed main(){
	cin>>n>>s;
	cin>>str;
	for(int i=0;i<str.size();i++){
		if(str[i]=='U'){
			if(s==1)continue;//根节点没有父节点
			if(t){
				t--;//抵消
				continue;
			}
			s/=2;
		}
		if(str[i]=='L'){
			if(2*s>inf)t++;//不进行移动，记录下来。
			else s*=2;
		}
		else if(str[i]=='R'){
			if(2*s+1>inf)t++;//同上。
			else s=s*2+1;
		}
	}
	cout<<s<<endl;
	return 0;
}