GESP2024年12月认证C++六级( 第三部分编程题（1）树上游走）

参考程序：

#include <iostream>
#include <string>using namespace std;int main() {long long n, s;  // n为移动次数，s为初始节点编号string moves;    // 移动指令串// 输入处理cin >> n >> s;cin >> moves;long long currentNode = s;  // 当前节点编号// 遍历每个移动指令并进行操作for (char move : moves) {if (move == 'U') {if (currentNode > 1) {currentNode /= 2;  // 向上移动到父节点}} else if (move == 'L') {currentNode = 2 * currentNode;  // 向左移动到左儿子} else if (move == 'R') {currentNode = 2 * currentNode + 1;  // 向右移动到右儿子}}// 输出最终的节点编号cout << currentNode << endl;return 0;
}

程序改进（引入栈与位运算实现数据防溢出）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e12;
int n;
stack<char> st;
string c;
ll s;
int main()
{cin >> n >> s >> c;for(int i = 0; i < n; i ++){if(c[i] == 'U'){if(s == 1) continue;if(st.size()){st.pop();continue;}s >>= 1;}else if(c[i] == 'L'){if((s << 1) > INF){st.push('L');continue;}s = s << 1;}else{if((s << 1 | 1) > INF){st.push('R');continue;}s = s << 1 | 1;}}cout << s << "\n";return 0;
}