在无穷完全二叉树上按 U/L/R 指令移动 n 次,求最终结点编号。
有一棵包含无穷节点的完全二叉树:根结点编号 1,结点 i 的左儿子是 2i、右儿子是 2i+1,父结点是 ⌊i/2⌋。
从结点 s 出发,按长度为 n 的指令串移动,每次是三种之一:
U:向上到父结点;若已在根(无父结点)则原地不动L:移动到左儿子R:移动到右儿子求 n 次移动后的结点编号(保证最终编号不超过 10¹²)。
U → s /= 2(整除);L → s = 2s;R → s = 2s + 1。完全二叉树编号父子关系公式逐指令模拟边界处理
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、s;第二行长度 n 的指令串 |
| 输出 | 最终结点编号 |
| 数据范围 | 1 ≤ n ≤ 10⁶,1 ≤ s ≤ 10¹² |
| 指令 | 仅含大写字母 U、L、R |
| 保证 | 最终结点编号 ≤ 10¹² |
2i、右儿子 2i+1、父结点 i/2——这正是完全二叉树的顺序存储编号方式s = 1 时执行 U 应当原地不动(因为根没有父结点)一步步模拟。
2 的二进制是 10₂
s = 2
2 有父结点(因为 2 > 1)
s = 2 / 2 = 1
现在到了根
s = 1
s = 2 × 1 + 1 = 3
s = 3
s = 2 × 3 + 1 = 7
s = 7
最终 7 ✓(路径 2 → 1 → 3 → 7)
7 = 111₂:去掉最高位 1 得 11,表示"右、右"——正好对应路径 1 → 3 → 7 ✓。这个理解能帮你快速心算任意编号的位置。这两点是本题唯一的坑。
| 情形 | 输入 | 结果 | 说明 |
|---|---|---|---|
| 在根执行 U | n=1, s=1, "U" | 1 | 根没有父结点,原地不动 |
| 连续 U 到根后再 U | n=3, s=4, "UUU" | 1 | 4 → 2 → 1 → 1(第三次不动) |
| 编号变大 | n=40, s=1, "R"×40 | 2⁴⁰ − 1 | 需要用 long long(约 10¹²) |
起点 4
第 1 个 U:4/2 = 2
第 2 个 U:2/2 = 1
第 3 个 U:s = 1,已在根 → 不移动
结果 1
✅ 1
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!按 U/L/R 依次更新 s,注意根边界
U 且 s > 1 → s /= 2;L → s = 2*s;R → s = 2*s + 1。全部用 long long。把编号转成二进制路径,直接对路径做增删操作
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 逐指令模拟 | O(n) | 约 15 行 |
| 二进制路径法 | O(n)(同级) | 约 30 行 |
第一行输入 n 和 s,第二行输入指令串,程序会逐步模拟并展示路径。
点按钮开始 →
#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") 时忘记开足够大的字符数组。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 2 | 7 | 题面样例(2 → 1 → 3 → 7) |
1 1 | 1 | 在根执行 U,原地不动 |
3 4 | 1 | 4 → 2 → 1 → 1 |
2 1 | 5 | 1 → 左儿子 2 → 右儿子 5 |
3 1 | 8 | 一路向左:1 → 2 → 4 → 8 |
1 1000000000000 | 500000000000 | 大编号处理,验证 long long |
2s+1 更是超出 int,必须 long long。1/2 = 0,会导致编号变成 0。2s、右儿子 2s+1。需要存下 n 个字符的指令串。
✅ 约 100 万次操作,瞬间完成。本题属于"考细心"的模拟题,难点全在边界和类型上。
// 完全二叉树(堆式)编号的父子关系 // 父结点: 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 与距离 |