GESP 题解库 / 6 级题解 / [GESP202412 六级] 树上游走 · 第 12 / 27 题
GESP202412 六级 · P11375 · 入门

树上游走

在无穷完全二叉树上按 U/L/R 指令移动 n 次,求最终结点编号。

📊
n ≤ 10⁶
移动次数
🔢
long long
编号范围
⚡
O(n)
时间复杂度
🎯
二叉树编号与父子关系
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有一棵包含无穷节点的完全二叉树:根结点编号 1,结点 i 的左儿子是 2i、右儿子是 2i+1,父结点是 ⌊i/2⌋。

从结点 s 出发,按长度为 n 的指令串移动,每次是三种之一:

求 n 次移动后的结点编号(保证最终编号不超过 10¹²)。

💡
人话翻译:直接按指令逐条模拟就行。
U → s /= 2(整除);L → s = 2s;R → s = 2s + 1。
唯一要注意的是"在根时 U 不动"这个边界,以及编号可能达到 10¹² 量级(必须用 long long)。

🔍 关键词提取

完全二叉树编号父子关系公式逐指令模拟边界处理

已知条件

项目说明
输入第一行 n、s;第二行长度 n 的指令串
输出最终结点编号
数据范围1 ≤ n ≤ 10⁶,1 ≤ s ≤ 10¹²
指令仅含大写字母 U、L、R
保证最终结点编号 ≤ 10¹²

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 编号就是"路径编码"
🔢 编号规则
根 = 1
左儿子 = 2i
右儿子 = 2i+1
父结点 = ⌊i/2⌋
🔁 三种操作
U:s 整除 2
L:s 变成 2s
R:s 变成 2s+1
逐条模拟
🧠 巧妙理解
编号的二进制形式 = 路径
1 表示根
后面每位:0 是左、1 是右
如 13 = 1101 → 根-右-左-右
⚠️ 易错点
用 int(s 可达 10¹²)
s = 1 时 U 没有原地不动
把 L、R 写成 2s、2s+1 时溢出
读入指令串长度不对
03
样例手算推导
样例与编号规律的验证

🧮 样例:n = 3,s = 2,指令 "URR"

一步步模拟。

1
起点:结点 2

2 的二进制是 10₂

s = 2

2
第 1 步 U(向上)

2 有父结点(因为 2 > 1)

s = 2 / 2 = 1

现在到了根

s = 1

3
第 2 步 R(右儿子)

s = 2 × 1 + 1 = 3

s = 3

4
第 3 步 R(右儿子)

s = 2 × 3 + 1 = 7

s = 7

最终 7 ✓(路径 2 → 1 → 3 → 7)

🔑
编号的二进制形式就是"从根出发的路径":把编号写成二进制,去掉最高位的那个 1,剩下的位从左到右依次表示"往左(0)还是往右(1)"。
例如 7 = 111₂:去掉最高位 1 得 11,表示"右、右"——正好对应路径 1 → 3 → 7 ✓。这个理解能帮你快速心算任意编号的位置。

🧮 边界与溢出验证

这两点是本题唯一的坑。

情形输入结果说明
在根执行 Un=1, s=1, "U"1根没有父结点,原地不动
连续 U 到根后再 Un=3, s=4, "UUU"14 → 2 → 1 → 1(第三次不动)
编号变大n=40, s=1, "R"×402⁴⁰ − 1需要用 long long(约 10¹²)
1
4 → 2 → 1 → 1 的逐步过程

起点 4

第 1 个 U:4/2 = 2

第 2 个 U:2/2 = 1

第 3 个 U:s = 1,已在根 → 不移动

结果 1

✅ 1

2
为什么必须用 long long?

s 本身可达 10¹²

执行一次 R:2s + 1 可达约 2 × 10¹²

这已经超出 int 上限(约 2.1 × 10⁹)

所以必须用 long long

用 long long

⚠️
关于"原地不动"的实现:最自然的写法是 if (s > 1) s /= 2;。如果写成 s /= 2 不加判断,s = 1 时结果还是 1(因为 1/2 = 0 在整除下……)注意:C++ 里 1 / 2 = 0,所以不加判断会得到 0 而不是 1!
这是本题最常见的失分点。
04
解法对比
直接模拟 vs 二进制路径转换

⚔️ 解法对比

🟢 逐指令模拟(推荐) 推荐

按 U/L/R 依次更新 s,注意根边界

  • 时间 O(n)
  • n = 10⁶ 时约 10⁶ 次
  • 代码 15 行
  • 直观、不易错
💡
三个更新式:U 且 s > 1 → s /= 2;L → s = 2*s;R → s = 2*s + 1。全部用 long long。

🟠 用二进制路径直接算

把编号转成二进制路径,直接对路径做增删操作

  • 思路巧妙但对本题没必要
  • 边界处理更麻烦
  • 本题 n 只有 10⁶,模拟足够快
  • 适合做"理解方式"
⚠️
什么时候值得用二进制视角:如果 n 极大(如 10¹⁸)而需要快速跳跃,二进制/位运算会更高效。本题只需要"理解"这个视角,代码还是模拟最稳。

📈 性能对比

方案复杂度代码量
逐指令模拟O(n)约 15 行
二进制路径法O(n)(同级)约 30 行
05
算法流程图
逐条指令模拟移动
开始读入 n、s 和长度为 n 的指令串i 从 0 遍历到 n − 1指令是否为 U?是 ✓若 s 大于 1 则 s = s / 2(否则原地不动)否 ✗再看是 L 还是 R指令是否为 L?是 ✓s = 2 × s(左儿子)否 ✗s = 2 × s + 1(右儿子)继续处理下一条指令输出最终的 si 加 1 处理下一条
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 游走终点计算器

第一行输入 n 和 s,第二行输入指令串,程序会逐步模拟并展示路径。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long s;                     // 必须用 long long!
    scanf("%d %lld", &n, &s);

    string mv;
    cin >> mv;

    for (int i = 0; i < n; i++) {
        if (mv[i] == 'U') {
            if (s > 1) s /= 2;       // 在根(s == 1)时原地不动
        } else if (mv[i] == 'L') {
            s = 2 * s;               // 左儿子
        } else {                     // 'R'
            s = 2 * s + 1;           // 右儿子
        }
    }

    printf("%lld\n", s);
    return 0;
}
🔑
为什么 U 一定要加 if (s > 1)?因为 C++ 的整数除法是"向零取整",1 / 2 = 0。如果不加判断,在根结点执行 U 会让编号变成 0,而 0 不是合法的结点编号,后续所有操作都会出错。
这个"根结点"的边界是本题唯一的坑,也是"读题要读全"(题目明确写了"否则不移动")的典型例子。

📖 关键几行怎么看

代码作用为什么这样写
long long s类型s 可达 10¹²,2s+1 可达 2 × 10¹²
if (s > 1) s /= 2;U 操作根结点原地不动
s = 2 * s;L 操作左儿子编号
s = 2 * s + 1;R 操作右儿子编号
cin >> mv读指令串不含空格,直接读入
⚠️
四个坑:① 用 int(s 可达 10¹²,会溢出);② U 操作没有判断根结点(会导致编号变 0);③ 把 L、R 的公式写反;④ 用 scanf("%s") 时忘记开足够大的字符数组。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 2
URR
7题面样例(2 → 1 → 3 → 7)
1 1
U
1在根执行 U,原地不动
3 4
UUU
14 → 2 → 1 → 1
2 1
LR
51 → 左儿子 2 → 右儿子 5
3 1
LLL
8一路向左:1 → 2 → 4 → 8
1 1000000000000
U
500000000000大编号处理,验证 long long
✅
自查清单:① 用 long long 吗?② U 判根了吗?③ L、R 公式对吗?

🚨 易错点清单

⚠️
用 int:s 可达 10¹²,2s+1 更是超出 int,必须 long long。
⚠️
U 没判根:1/2 = 0,会导致编号变成 0。
⚠️
公式写反:左儿子 2s、右儿子 2s+1。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
10⁶
运算量
约 10⁶

时间怎么算的?

空间都用在哪?

需要存下 n 个字符的指令串。

✅ 约 100 万次操作,瞬间完成。本题属于"考细心"的模拟题,难点全在边界和类型上。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 完全二叉树(堆式)编号的父子关系
// 父结点: i / 2
// 左儿子: 2 * i
// 右儿子: 2 * i + 1
// 是否为左儿子: i 为偶数
// 是否为右儿子: i 为奇数(且 i > 1)
// 层号(从 0 开始): floor(log2(i))

// 编号 → 路径(二进制视角)
// 把 i 写成二进制,去掉最高位的 1,
// 剩下的每一位:0 表示"向左",1 表示"向右"
// 例如 13 = 1101 -> 去掉首位得 101 -> 右、左、右

// 求 LCA(最小公共祖先)的简单写法(利用编号性质)
while (a != b) {
    if (a > b) a /= 2;
    else b /= 2;
}

// 求两点距离
int dist(int a, int b) {
    int d = 0;
    while (a != b) {
        if (a > b) a /= 2; else b /= 2;
        d++;
    }
    return d;
}

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
堆式编号父子关系 O(1) 计算完全二叉树、堆、线段树
二进制即路径编号与路径一一对应快速心算结点位置
同时上跳求 LCA深者先跳完全二叉树上的 LCA 与距离
🌟
思考题:如果指令串里出现了连续很多个 U(比如 10⁶ 个 U 而 s 很小),有没有办法加速?(提示:可以用位运算——先把 s 的位数算出来,多余的 U 直接跳过(因为在根不动)。不过本题 n 只有 10⁶,直接模拟完全够快,不必过度优化。)