G6011 [GESP202412 六级] 树上游走 题解

知识点：二叉树、栈、二进制路径。

解题思路

把起点编号转为二进制路径，U删除末尾一位，L追加0，R追加1，操作完成后再还原整数。

为什么正确

堆式二叉树编号满足左子2x、右子2x+1、父节点floor(x/2)，因此位串操作与树上移动完全等价。

易错点

不能每走一步都立即转成长整型，否则中间深度可能溢出；根处U按题目规则处理。

复杂度

时间O(n+log起点)，空间O(n+log起点)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long start;
    cin>>n>>start;
    string s,path;
    cin>>s;
    while(start) {
        path+=char('0'+start%2);
        start/=2;
    }
    reverse(path.begin(),path.end());
    for(char c:s) {
        if(c=='U') {
            if(path.size()>1)path.pop_back();
        }
        else path+=(c=='L'?'0':'1');
    }
    long long ans=0;
    for(char c:path)ans=ans*2+c-'0';
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。