小信跳房子的题解

原题描述：

时间：1s 空间：256M

题目描述：

小信在玩跳房子游戏，已知跳房子游戏的图表现为一颗完美的具有个节点的二叉树。从根节点依次编号为。节点的左子节点编号为，右子节点编号为。

小信从从节点出发，共跳步，用一个长度为的字符串表示小信的移动方向，“U”表示跳到当前所在节点的父节点，“L”表示跳到当前节点的左子节点，“R”表示跳到当前节点的右子节点。

输出小信在跳了步之后所处的节点编号，保证最终答案不超过。

提示：在跳的过程中节点编号可能超过。

输入格式：

第一行包含两个整数，表示小信移动次数和初始所在节点编号。

第二行包含一个只含“U”，“L”和“R”的长为的字符串。

输出格式：

输出一个整数，表示小信在跳了步之后所处的节点编号。

样例1输入：

3 2
URL

样例1输出：

6

样例2输入：

6 500000000000000000
RRRUUU

样例2输出：

500000000000000000

约定与提示：

对于100%的数据，,

样例1：小信的移动路径是2 -> 1 -> 3 -> 6

题目大意：

有一个人，再完全二叉树的x节点，求他跳动n此后在哪个节点，给定每次怎么跳动。

主要思路：

这个题是用硬枚举，但枚举时会爆掉，有人说用__int128，但还是爆，所以要消除一些无用操作（题目保证结果<=)

当操作是U时，我们发现x = x/2(向下取整，long long 自动向下取整）

当操作是R时，我们发现x = x*2+1

当操作是L时，我们发现x = x*2

我们发现LU，RU这些操作组可以不执行。

LU：

RU:

我们用一个vector<char>(设为v)记录一下操作的过程。

当v.back() 不是U且v非空且当前插入进来的字符是U，那么就可以抵消，把v.back删掉（由于插入时是push_back()，所以上一个插入的是在最尾端，就是v.back() )。

否则就插入一个操作符。

这样就不会爆了。

最后遍历一遍v,根据题目要求操作就可以了。

注意事项：

1. 一定要开long long。
2. UL和UR是不能抵消的，具体请看下图。

?

代码code：

#include<bits/stdc++.h>
using namespace std;
long long n,x;//开long long
vector<char> st;
int main()
{
	cin>>n>>x;
	string s;
	cin>>s;
	for(int i=0;i<n;i++)
	{
		if(s[i] == 'U'&&!st.empty()&&st.back()!='U')//如果可以抵消
		{
			st.pop_back();
		}
		else
		{
			st.push_back(s[i]);
		}
	}
	for(int i=0;i<st.size();i++)//开始操作
	{
		if(st[i] == 'U')
		{
			x = x/2;
		}
		else if(st[i] == 'L')
		{
			x*=2;
		}
		else
		{
			x*=2;
			x++;
		}
	}
	cout<<x;
	return 0;
}