9751.树上游走

markdown
复制
1# 树上游走 题解
2
3## 题目分析
4
5本题描述了一棵拥有无穷多个节点的完全二叉树，节点的编号规则如下：
6
7- 根节点编号为 $1$。
8- 对于编号为 $i$ 的节点，左儿子编号为 $2i$，右儿子编号为 $2i+1$。
9
10小杨从初始节点 $s$ 出发，进行 $n$ 次移动。每次移动有三种可能，用一个长度为 $n$ 的字符串给出：
11
12- `'U'`：向上走到父节点（若当前为根节点 $1$ 则不动）。
13- `'L'`：向左走到左儿子。
14- `'R'`：向右走到右儿子。
15
16题目保证 **最终** 到达的节点编号不超过 $10^{12}$。我们需要输出最终的节点编号。
17
18## 解题思路
19
20### 直接模拟的问题
21
22最直接的想法是按照字符串指令一步步移动，维护当前节点编号 `s`。移动规则对应位运算：
23
24- `U`：如果 `s != 1`，则 `s = s / 2`（即 `s >>= 1`）。
25- `L`：`s = s * 2`（即 `s <<= 1`）。
26- `R`：`s = s * 2 + 1`（即 `s = s << 1 | 1`）。
27
28但问题在于：虽然最终节点编号 $\le 10^{12}$，但中间过程中节点编号可能会远远超过 $10^{12}$，甚至超出 `long long` 的范围。如果简单地直接计算，可能会发生溢出或产生不必要的巨大数字。
29
30### 关键观察
31
32题目保证 **最终** 节点编号不超过 $10^{12}$。这意味着，所有使得节点编号超过 $10^{12}$ 的向下移动（`L` 或 `R`），**必定会在后续的向上移动 `U` 中被完全抵消**。否则，最终编号不可能回到 $10^{12}$ 以内。
33
34例如，当前节点 $s = 6 \times 10^{11}$，执行 `L` 后编号变为 $1.2 \times 10^{12} > 10^{12}$。如果之后没有执行 `U`，最终节点编号就会大于 $10^{12}$，与题目保证矛盾。因此，这些“越界”的向下移动一定会被后续的 `U` 一一撤销。
35
36### 使用栈或计数器优化
37
38利用上述性质，我们可以 **不必真实执行** 那些会导致越界的向下移动，而是将它们“暂存”起来：
39
40- 当遇到 `L` 或 `R` 时，计算执行后的编号。若 **大于 $10^{12}$**，则不修改当前编号 `s`，而是将这次操作记录在栈中（或简单地用一个计数器记录未撤销的越界向下次数）。
41- 当遇到 `U` 时：
42  - 如果当前节点已经是根节点 $1$，则忽略。
43  - 如果 **栈非空**（或计数器 $>0$），说明之前有未撤销的越界向下移动。此时我们可以**直接弹出栈顶（计数器减 $1$）**，表示这次向上移动和一次越界向下移动互相抵消，**节点编号不变**。
44  - 如果栈为空（计数器为 $0$），则没有待抵消的越界移动，正常执行向上移动 `s >>= 1`。
45
46这样处理，`s` 始终保持在一个不超过 $10^{12}$ 的真实节点编号上，中间过程不会产生巨大的数，计算量也大大减少。
47
48### 为什么可以不区分 `L` 和 `R` 直接抵消？
49
50在抵消时，我们不需要知道越界的那次移动是左移还是右移。因为无论当时是向左还是向右，只要它使得编号大于 $10^{12}$，其后的一个 `U` 必然会让节点**原路返回**到移动前的那个节点。因此，向上与向下的两次操作成对抵消，最终编号不变。这使得我们可以直接使用一个整数计数器来替代栈。
51
52## 算法步骤
53
541. 读入 $n$、$s$ 和操作字符串。
552. 初始化一个计数器 `cnt = 0`（或者栈）。
563. 遍历操作字符串中的每个字符 `c`：
57   - 若 `c == 'U'`：
58     - 如果 `s == 1`，跳过；
59     - 如果 `cnt > 0`，则 `cnt--`；
60     - 否则 `s >>= 1`。
61   - 若 `c == 'L'`：
62     - 如果 `s * 2 > 1e12`，则 `cnt++`；
63     - 否则 `s = s * 2`。
64   - 若 `c == 'R'`：
65     - 如果 `s * 2 + 1 > 1e12`，则 `cnt++`；
66     - 否则 `s = s * 2 + 1`。
674. 输出 `s`。
68
69题目的 C++ 参考代码使用了栈来存储具体的 `'L'` 或 `'R'`，其逻辑与计数器完全等价，读者可以根据喜好实现。
70
71## 时间复杂度分析
72
73我们只需遍历一次长度为 $n$ 的字符串，每次操作都是 $O(1)$ 的位运算或栈/计数器操作。因此：
74
75- **时间复杂度**：$O(n)$。
76- **空间复杂度**：$O(1)$（使用计数器）或 $O(n)$（使用栈，最坏情况下栈大小可能达到 $n$，但 $n \le 10^6$，完全在内存限制内）。
77
78## 参考代码及解释
79
80下面给出与题目 C++ 参考代码等价的实现，并添加了详细注释。该代码使用栈来实现“暂存”与“抵消”。
81
82```cpp
83#include <bits/stdc++.h>
84#define ll long long
85using namespace std;
86
87const ll INF = 1e12;          // 题目保证最终节点不超过 1e12
88
89int n;
90stack<char> st;              // 栈，用于记录越过 INF 的向下移动
91string c;
92ll s;
93
94int main() {
95    cin >> n >> s >> c;
96
97    for (int i = 0; i < n; ++i) {
98        if (c[i] == 'U') {
99            if (s == 1) continue;   // 根节点无法向上
100            if (!st.empty()) {      // 栈中有待抵消的向下移动
101                st.pop();           // 抵消一次向下移动，编号不变
102                continue;
103            }
104            s >>= 1;                // 没有越界移动，真正向上
105        } else if (c[i] == 'L') {
106            if ((s << 1) > INF) {   // 越界，不真正移动，入栈
107                st.push('L');
108                continue;
109            }
110            s = s << 1;             // 正常向左移动
111        } else { // c[i] == 'R'
112            if ((s << 1 | 1) > INF) { // 越界，入栈
113                st.push('R');
114                continue;
115            }
116            s = s << 1 | 1;         // 正常向右移动
117        }
118    }
119
120    cout << s << "\n";
121
122    return 0;
123}

代码解释

• s << 1 等价于 $s \times 2$，s << 1 | 1 等价于 $s \times 2 + 1$。使用位运算更加高效。
• 当检测到 L 或 R 将导致编号超过 1e12 时，我们不修改 s，而是将操作符压入栈中。这意味着当前节点编号保持不变，后续的 U 将优先与栈中的操作抵消。
• 遇到 U 时：
  • 如果栈非空，弹出一个元素，相当于撤销一次之前“欠下”的向下移动，节点编号不变。
  • 如果栈为空，则说明没有越界的向下操作需要抵消，此时才是真正需要向上移动的情况，执行 s >>= 1。
• 根节点 $1$ 无法向上，遇到 U 时直接跳过。

更简洁的计数器写法

本题中，我们其实不关心栈里具体是 'L' 还是 'R'，只需要知道有多少次“待抵消的移动”。因此可以用一个整数 cnt 代替栈，代码会变得更加简洁，并且空间复杂度降为 $O(1)$。有兴趣的同学可以自行尝试实现。

总结

本题的关键在于发现 越界操作必然成对抵消 的性质，从而避免直接计算超大的节点编号。这种“不实际执行，用栈/计数器暂存并延迟抵消”的技巧，在处理具有撤销操作且中间状态可能越界的问题时非常实用，值得掌握。