欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P11375 GESP202412 六级] 树上游走 - 洛谷
【题目描述】
小杨有一棵包含无穷节点的二叉树（即每个节点都有左儿子节点和右儿子节点；除根节点外，每个节点都有父节点），其中根节点的编号为1 11，对于节点i ii，其左儿子的编号为2 × i 2\times i2×i，右儿子的编号为2 × i + 1 2\times i + 12×i+1。
小杨会从节点s ss开始在二叉树上移动，每次移动为以下三种移动方式的任意一种：
- 第 1 种移动方式：如果当前节点存在父亲节点，向上移动到当前节点的父节点，否则不移动；
- 第 2 种移动方式：移动到当前节点的左儿子；
- 第 3 种移动方式：移动到当前节点的右儿子。
小杨想知道移动n nn次后自己所处的节点编号。数据保证最后所处的节点编号不超过10 12 10^{12}1012。
【输入】
第一行包含两个正整数n nn和s ss，代表移动次数和初始节点编号。
第二行包含一个长度为n nn且仅包含大写字母U \tt{U}U、L \tt{L}L和R \tt{R}R的字符串，代表每次移动的方式，其中U \tt{U}U代表第 1 种移动方式，L \tt{L}L代表第 2 种移动方式，R \tt{R}R代表第 3 种移动方式。
【输出】
输出一个正整数，代表最后所处的节点编号。
【输入样例】
3 2 URR【输出样例】
7【算法标签】
《洛谷 P11375 树上游走》 #模拟# #高精度# #栈# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long类型，防止溢出intn;// 操作序列的长度intx;// 当前节点编号string s;// 操作序列deque<char>dq;// 双端队列，用于存储简化后的操作signedmain()// 因为定义了#define int long long，所以用signed代替int{// 输入：操作序列长度n，初始节点x，操作序列scin>>n>>x>>s;// 在字符串前加空格，使下标从1开始，方便处理s=" "+s;// 第一步：简化操作序列// 核心思想：删除无用的操作对（如LRU、LUR、RLU、RUL等）for(inti=1;i<=n;i++){if(dq.empty()){// 如果队列为空，直接加入当前操作dq.push_back(s[i]);}elseif(dq.back()!='U'&&s[i]=='U'){// 关键优化：如果队列尾部不是'U'且当前操作是'U'// 那么前一个操作和当前的'U'会相互抵消// 例如：'L'+'U' = 回到原位置，'R'+'U' = 回到原位置dq.pop_back();// 删除前一个操作}else{// 其他情况，直接加入当前操作dq.push_back(s[i]);}}// 第二步：执行简化后的操作序列while(!dq.empty()){charc=dq.front();// 从队列头部取操作dq.pop_front();// 删除已取出的操作if(c=='U'&&x>1){// 'U'：移动到父节点x/=2;// 在完全二叉树中，父节点编号是子节点编号除以2}elseif(c=='L'){// 'L'：移动到左子节点x*=2;// 左子节点编号是当前节点编号乘以2}elseif(c=='R'){// 'R'：移动到右子节点x=x*2+1;// 右子节点编号是当前节点编号乘以2加1}}// 输出最终节点编号cout<<x<<endl;return0;}【运行结果】
3 2 URR 7
