变长编码 题解

题目分析

本题要求将一个非负整数 $N$ 转换成一种“变长编码”。这种编码的核心思想是：用尽可能少的字节表示较小的数，同时也能灵活地表示大数。

题目给出的编码规则可以概括为三步：

1. 二进制拆分：将整数转为二进制。
2. 按7位分组：从低位到高位，每7位一组，不足7位的高位补0。
3. 添加标志位：在每个7位组的最高位之前添加一个标志位。如果是最后一组（即最高位所在的组），标志位填0；否则填1。这样每组变成了8位（即一个字节）。

最后，将这若干个字节用十六进制形式输出，字节之间用空格隔开。

举个例子：

• $N = 0$：
  • 二进制为 0，补足7位得到 0000000。
  • 只有一组，是最后一组，标志位填0，得到 00000000，即 00。
• $N = 926$：
  • 二进制为 1110011110（共10位）。
  • 从低到高每7位一组：低7位 0011110，高3位补4个0变成 0000111。
  • 低组不是最后一组，标志位填1 → 10011110（即 0x9E）。
  • 高组是最后一组，标志位填0 → 00000111（即 0x07）。
  • 输出顺序是 由低组到高组，因此输出 9E 07。

题目要求 $0 \le N \le 10^{18}$，所以 $N$ 最大不会超过 $2^{60}$，对应的组数最多为 $60/7 \approx 9$ 组，完全可以用数组存储。

---

解题思路

根据规则，我们可以模拟整个过程：

1. 提取每一组：
   使用位运算，每次取 $N$ 的二进制最低 7 位（可以通过 n & 0x7F 得到），然后将 $N$ 右移 7 位，继续提取下一组，直到 $N$ 变为 0。
2. 设置标志位：
   最高位的一组（即数组中的最后一个元素）保持最高位为 0；其余各组需要在最高位填 1（即 | 0x80）。
3. 输出：
   按提取的顺序（从低组到高组）依次输出每个字节的十六进制表示。注意十六进制字母要大写，且一个字节对应两位十六进制。

对于 $N = 0$ 的情况，按照规则也会输出一个字节 00，需要特殊处理。

---

算法说明

我们采用数组（或向量）来存储拆分出的 7 位组。算法流程如下：

1. 读入长整型 $N$。
2. 特判：如果 $N = 0$，直接输出 00 并结束。
3. 循环，当 $N>0$ 时：
   • 将 N & 0x7F 存入数组。
   • N >>= 7，继续循环。
4. 循环结束后，数组下标 $0$ 存储的是最低的 7 位组，下标逐渐增大，最高组在最后。
5. 遍历数组前 l-1 个元素（除了最后一组），把它们与 0x80 做按位或运算，给最高位填 1。
6. 最后，从数组头到尾依次输出每个字节的十六进制形式：
   • 高 4 位：(s >> 4) & 0x0F。
   • 低 4 位：s & 0x0F。
   • 将 4 位整数转换为对应字符：0~9 转为 '0'_{'9'，10}15 转为 'A'~'F'。

每输出一个字节前，如果不是第一个字节，先输出一个空格。

---

参考代码解读

下面是题目中给出的 C++ 参考代码，并辅以详细注释：

cpp
复制
1#include <iostream>
2using namespace std;
3
4// 输出4位对应的十六进制字符
5void output_digit(int d) {
6    if (d >= 10)
7        cout << (char)('A' + d - 10);   // 10→A, 11→B ... 15→F
8    else
9        cout << (char)('0' + d);        // 0→0 ... 9→9
10}
11
12// 输出一个字节的两位十六进制
13void output_code(int s) {
14    output_digit(s >> 4);       // 高4位
15    output_digit(s & 0x0f);     // 低4位
16}
17
18int main() {
19    long long n = 0;
20    cin >> n;
21    
22    // 特判 n == 0 的情况（原代码未处理，这里需要补充）
23    if (n == 0) {
24        cout << "00" << endl;
25        return 0;
26    }
27    
28    int split[10];  // 最多 10 组，足够
29    int l = 0;      // 组的个数
30
31    // 从低位到高位，每7位分成一组
32    while (n > 0) {
33        split[l] = (int)(n & 0x7f);   // 取最低的7位
34        n >>= 7;                      // 右移7位
35        l++;
36    }
37
38    // 除了最后一组（最高组），其他组最高位填 1
39    for (int i = 0; i < l - 1; i++)
40        split[i] |= 0x80;
41
42    // 按顺序输出（低组到高组）
43    output_code(split[0]);
44    for (int i = 1; i < l; i++) {
45        cout << " ";
46        output_code(split[i]);
47    }
48    cout << endl;
49    return 0;
50}

代码解释：

• output_digit 将 0~15 的值转为十六进制字符输出。
• output_code 将一个字节拆成高4位和低4位，分别调用 output_digit 输出。
• split 数组用来按顺序存储每一组。l 记录组数。
• 提取7位使用掩码 0x7f（二进制 0111 1111），右移7位相当于“扔掉”已经处理过的低位。
• 拆分完成后，split[0] 是最低7位组，split[l-1] 是最高7位组。
• 根据规则，最高组标志位填0，其余填1。因此，只需要把下标 0 到 l-2 的组最高位设置为1（|= 0x80，0x80 即 1000 0000）。
• 输出时以空格分隔各个字节。

注意：原参考代码未处理 $n = 0$ 的特殊情况。若不处理，while 循环一次都不执行，l 为 0，后面访问 split 数组会出现越界或输出异常。因此实际编写时需要加入 n == 0 的判断。

---

时间复杂度分析

每一轮循环将 $N$ 右移 7 位。当 $N$ 最大为 $10^{18} \approx 2^{60}$ 时，最多循环 $\lceil 60/7 \rceil = 9$ 次。因此循环次数是一个很小的常数（与输入规模的对数相关）。

输出时每个字节调用两次 output_digit，组数最多同样为 9，因此总体时间复杂度为 $O(\log N)$，在本题中可以看作 $O(1)$。空间复杂度也只需要一个很小的数组，为 $O(1)$。

---

总结

本题主要考察位运算和进制转换的基本功。只要理解了“每7位分组，除最后一组外最高位填1”这一规则，剩下的就是用掩码和移位操作来模拟整个过程了。需要留意的细节是十六进制的大写输出，以及 $N=0$ 的边界处理。