【GESP】C++四级真题 luogu-B3870 [GESP202309 四级] 变长编码
GESP C++四级2023年9月真题，函数、位运算等应用，难度⭐⭐★☆☆。个人认为23年GESP考试设立初期各级考试的题难度相对较高，本题在洛谷评定为普及-。
luogu-B3870 [GESP202309 四级] 变长编码
题目要求
题目描述
小明刚刚学习了三种整数编码方式：原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得，生活中很少用到 $2^{31}-1$ 这么大的数，生活中常用的 $0 \sim 100$ 这种数也同样需要用 $4$ 个字节的补码表示，太浪费了些。 热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下：
1.对于给定的正整数，首先将其表达为二进制形式。例如， \((0)_{\{10\}}=(0)_{\{2\}}\)
和
\[(926)_{\{10\}}=(1110011110)_{\{2\}}\]2.将二进制数从低位到高位切分成每组 $7$ bit，不足 $7$ bit 的在高位用 $0$ 填补。例如，
\[(0)_{\{2\}}\]变为 $0000000$ 的一组，
\[(1110011110)_{\{2\}}\]变为 $0011110$ 和 $0000111$ 的两组。
3.由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上 $0$，否则在最高位填上 $1$。于是，$0$ 的变长编码为 $00000000$ 一个字节， $926$ 的变长编码为 $10011110$ 和 $00000111$ 两个字节。
这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如，$987654321012345678$ 的二进制为
\[(0001101 \ 1011010 \ 0110110 \ 1001011 \ 1110100 \ 0100110 \ 1001000 \ 0010110 \ 1001110)_{\{2\}}\]，于是它的变长编码为（十六进制表示）
CE 96 C8 A6 F4 CB B6 DA 0D，共 $9$ 个字节。你能通过编写程序，找到一个正整数的变长编码吗？
输入格式
输入第一行，包含一个正整数 $N$。约定 $0\le N \le 10^{18}$。
输出格式
输出一行，输出 $N$ 对应的变长编码的每个字节，每个字节均以 $2$ 位十六进制表示（其中，
A-F使用大写字母表示），两个字节间以空格分隔。
输入输出样例 #1
输入 #1
1
0
输出 #1
1
00
输入输出样例 #2
输入 #2
1
926
输出 #2
1
9E 07
输入输出样例 #3
输入 #3
1
987654321012345678
输出 #3
1
CE 96 C8 A6 F4 CB B6 DA 0D
题目分析
本题主要考察了二进制转换、位运算和字符串处理的能力。这里提供两种解决思路，供参考：
方法一：二进制字符串处理
这种方法的思路比较直观，主要步骤如下：
- 先将输入的十进制数转换成二进制字符串
- 从低位到高位每7位进行分组，不足7位的用0补齐
- 根据是否为最后一组，在每组最高位添加0或1标识位
- 最后将每组二进制转换为十六进制输出
这种方法的优点是思路清晰，容易理解和实现。缺点是需要进行字符串处理，效率相对较低。
方法二：位运算处理
这种方法直接使用位运算进行处理，主要步骤如下：
- 使用位与运算(&)每次取出最低7位
- 根据是否还有后续数据，设置当前字节的最高位(通过位或运算|)
- 将原数右移7位，继续处理下一组数据
- 最后将每个字节转换为十六进制输出
这种方法的优点是运算效率高，不需要进行字符串转换。缺点是位运算的代码相对理解起来有难度。
算法复杂度分析
方法一：二进制字符串处理
- 时间复杂度: $O(\log n)$，$n$ 为正整数的值。
- 将十进制数转换为二进制字符串需要 $O(\log n)$ 次除法运算
- 字符串分组和处理需要遍历整个二进制字符串，长度为 $O(\log n)$
- 每组转换为十六进制输出是常数时间 $O(1)$
- 空间复杂度: $O(\log n)$
- 需要存储二进制字符串，长度为 $O(\log n)$
- 存储结果数组，大小为 $O(\log n / 7) \approx O(\log n)$
方法二：位运算处理
- 时间复杂度: $O(\log n)$
- 每次右移7位，总共需要 $O(\lfloor \log n / 7 \rfloor) \approx O(\log n)$ 次操作
- 每次位运算和十六进制转换是常数时间 $O(1)$
- 空间复杂度: $O(\log n)$
- 只需要存储结果数组，大小为 $O(\lfloor \log n / 7 \rfloor) \approx O(\log n)$
虽然两种方法的渐进复杂度相同，且能正确解决问题，但在实际应用中，建议尽量理解和使用方法二，因为其执行效率更高，且在处理大数据时更有优势。
示例代码
方法一：转换成二进制字符串处理（思维最直接）
下面示例代码可能不是最简洁，但是步骤比较清晰，容易理解，不跳步。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
// 对整数n进行变长编码，返回编码后的字节序列
// 变长编码方式：每7位二进制为一组，最高位为1表示后续还有字节，最高位为0表示最后一个字节
std::vector<std::string> encode_variant(long long n) {
std::vector<std::string> result; // 存储编码结果
if (n == 0) { // 特殊情况：n为0时，直接返回"00"
result.push_back("00");
return result;
}
// 将n转换为二进制字符串（高位在前，低位在后）
std::string tmp;
while (n != 0) {
// 每次取最低位，拼接到tmp前面
tmp = char(n % 2 + '0') + tmp;
n /= 2;
}
int l_tmp = tmp.length(); // 二进制字符串长度
if (l_tmp <= 7) {
// 如果二进制长度不超过7位，直接补在后面，最高位为0，表示这是最后一个字节
result.push_back('0' + tmp);
} else {
// 如果超过7位，需要分组处理
int f_length = l_tmp % 7; // 头部不足7位的长度
int idx = l_tmp - 7; // 从倒数第7位开始分组
// 从高位到低位，每7位为一组，最高位为1，表示后续还有字节
while (idx >= 0) {
std::string cur_str = tmp.substr(idx, 7); // 取7位
result.push_back('1' + cur_str); // 最高位为1
idx -= 7;
}
// 如果有头部不足7位的部分，需要补0到7位，最高位为0，表示最后一个字节
if (f_length != 0) {
std::string tmp_str = tmp.substr(0, f_length); // 取头部不足7位
// 补0到7位
for (int j = 0; j < 7 - f_length; j++) {
tmp_str = '0' + tmp_str;
}
result.push_back('0' + tmp_str); // 最高位为0
}
}
return result; // 返回编码后的字节序列
}
int main() {
long long n;
std::cin >> n; // 从标准输入读取一个整数
// 对输入的整数进行变长编码
std::vector<std::string> result = encode_variant(n);
// 以16进制格式输出编码结果，每个字节宽度为2，前导补0，大写字母
for (std::string str : result) {
// 将二进制字符串转为整数，再以16进制输出
printf("%02X", stoll(str, nullptr, 2));
std::cout << " ";
}
return 0; // 程序结束
}
方法二：直接利用位运算取相应位的值（推荐）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
// 对整数n进行变长编码，返回编码后的字节序列
std::vector<long long> encode_variant(long long n) {
std::vector<long long> result; // 存储编码结果
if (n == 0) { // 特殊情况：n为0时，直接返回0
result.push_back(0);
return result;
}
// 当n不为0时，进行变长编码
while (n != 0) {
long long tmp = n & 0b1111111; // 取n的低7位
n >>= 7; // n右移7位，准备处理下一个字节
if (n != 0) {
tmp |= 0b10000000; // 如果后面还有数据，将最高位（第8位）设置为1，表示后续还有字节
}
result.push_back(tmp); // 将当前字节加入结果
}
return result; // 返回编码后的字节序列
}
// 将一个数字转换为两位十六进制并输出
// 参数 n: 要转换的数字
// 使用字符串索引方式将数字转为对应的十六进制字符
void print_hex(long long n) {
// 十六进制字符表，用于查找对应字符
std::string str = "0123456789ABCDEF";
// 输出高位(n/16)和低位(n%16)对应的十六进制字符
std::cout << str[n / 16] << str[n % 16];
}
int main() {
long long n;
std::cin >> n; // 从标准输入读取一个整数
std::vector<long long> result = encode_variant(n); // 对输入的整数进行变长编码
// 以16进制格式输出编码结果，每个字节宽度为2，前导补0，大写字母
for (long long i : result) {
print_hex(i);
std::cout << " ";
}
return 0; // 程序结束
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
