小信跳房子的题解

2024-01-01 01:12

文章标签 题解跳房子小信

本文主要是介绍小信跳房子的题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题描述：

时间：1s 空间：256M

题目描述：

小信在玩跳房子游戏，已知跳房子游戏的图表现为一颗完美的具有 $2^{10^{100}}-1$ 个节点的二叉树。从根节点依次编号为 $1,2,...,2^{10^{100}}-1$ 。节点 $i(1\le i \le 2^{10^{100}})$ 的左子节点编号为 $2i$ ，右子节点编号为 $2i+1$ 。

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

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

提示：在跳的过程中节点编号可能超过 $10^{18}$ 。

输入格式：

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

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

输出格式：

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

样例1输入：

3 2
URL

样例1输出：

样例2输入：

6 500000000000000000
RRRUUU

样例2输出：

500000000000000000

约定与提示：

对于100%的数据， $1 \le n \le 10^6$ , $1\le x\le 10^{18}$

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

题目大意：

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

主要思路：

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

当操作是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,根据题目要求操作就可以了。

注意事项：

一定要开long long。
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;
}

这篇关于小信跳房子的题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！