GESP认证C++编程真题解析 | B3870 [GESP202309 四级] 变长编码

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[B3870 GESP202309 四级] 变长编码 - 洛谷

【题目描述】

小明刚刚学习了三种整数编码方式：原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得，生活中很少用到2 31 − 1 2^{31}-1231−1这么大的数，生活中常用的0 ∼ 100 0\sim 1000∼100这种数也同样需要用4 44个字节的补码表示，太浪费了些。
热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下：

1. 对于给定的正整数，首先将其表达为二进制形式。例如，( 0 ) { 10 } = ( 0 ) { 2 } (0)_{\{10\}}=(0)_{\{2\}}(0){10}​=(0){2}​，( 926 ) { 10 } = ( 1110011110 ) { 2 } (926)_{\{10\}}=(1110011110)_{\{2\}}(926){10}​=(1110011110){2}​。
2. 将二进制数从低位到高位切分成每组7 77bit，不足7 77bit 的在高位用0 00填补。例如，( 0 ) { 2 } (0)_{\{2\}}(0){2}​变为0000000 00000000000000的一组，( 1110011110 ) { 2 } (1110011110)_{\{2\}}(1110011110){2}​变为0011110 00111100011110和0000111 00001110000111的两组。
3. 由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上0 00，否则在最高位填上1 11。于是，0 00的变长编码为00000000 0000000000000000一个字节，926 926926的变长编码为10011110 1001111010011110和00000111 0000011100000111两个字节。

这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如，987654321012345678 987654321012345678987654321012345678的二进制为( 0001101 1011010 0110110 1001011 1110100 0100110 1001000 0010110 1001110 ) { 2 } (0001101 \ 1011010 \ 0110110 \ 1001011 \ 1110100 \ 0100110 \ 1001000 \ 0010110 \ 1001110)_{\{2\}}(000110110110100110110100101111101000100110100100000101101001110){2}​，于是它的变长编码为（十六进制表示）CE 96 C8 A6 F4 CB B6 DA 0D，共9 99个字节。

你能通过编写程序，找到一个正整数的变长编码吗？

【输入】

输入第一行，包含一个正整数N NN。约定0 ≤ N ≤ 1 0 18 0\le N \le 10^{18}0≤N≤1018。

【输出】

输出一行，输出N NN对应的变长编码的每个字节，每个字节均以2 22位十六进制表示（其中，A-F使用大写字母表示），两个字节间以空格分隔。

【输入样例】

0

【输出样例】

00

【算法标签】

《洛谷 B3870 变长编码》 #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1005;intn;string a[N];// 存储分组后的二进制字符串/** * 十进制转二进制字符串 * @param x 十进制整数 * @return 二进制字符串 */stringDtoB(intx){string d="0123456789ABCDEF";// 数字字符表string ans="";// 不断除以2，取余数while(x>0){ans=d[x%2]+ans;// 余数转换为'0'或'1'，加到字符串前面x/=2;}returnans;}/** * 二进制字符串转十进制 * @param s 二进制字符串 * @return 十进制整数 */intBtoD(string s){intans=0;// 使用霍纳法则：ans = ans * 2 + 当前位for(inti=0;i<s.size();i++){ans=ans*2+(s[i]-'0');}returnans;}/** * 十进制转十六进制字符串 * @param x 十进制整数 * @return 十六进制字符串（至少两位，不足补0） */stringDtoH(longlongx){string d="0123456789ABCDEF",ans="";// 特判0的情况if(x==0){return"0";// 注意：这里返回"0"，但下面有补0处理}// 不断除以16，取余数while(x>0){ans=d[x%16]+ans;// 余数转换为十六进制字符x/=16;}// 如果结果只有一位，前面补0if(ans.length()==1){ans="0"+ans;}returnans;}signedmain(){cin>>n;// 特判输入为0的情况if(n==0){cout<<"00"<<endl;return0;}// 1. 十进制转二进制string s=DtoB(n);// 2. 从低位到高位，每7位一组（最后一组可能不足7位）intcnt=0;// 当前组内计数intcur=1;// 当前组号for(inti=s.size()-1;i>=0;i--)// 从低位（字符串末尾）开始{cnt++;a[cur]+=s[i];// 将当前位添加到当前组// 每7位一组if(cnt==7){cur++;// 开始新的一组cnt=0;}}// 3. 最后一组如果不足7位，用0补齐while(a[cur].size()<7){a[cur]+='0';}// 4. 为每组添加最高位（标识位）for(inti=1;i<cur;i++)// 前cur-1组，最高位为1（表示还有后续）{a[i]+='1';}a[cur]+='0';// 最后一组，最高位为0（表示结束）// 5. 反转每组字符串（因为是从低位开始构建的）for(inti=1;i<=cur;i++){reverse(a[i].begin(),a[i].end());}// 6. 将每组8位二进制转换为十六进制输出for(inti=1;i<=cur;i++){intt=BtoD(a[i]);// 二进制转十进制// cout << "t " << t << endl;string s=DtoH(t);// 十进制转十六进制cout<<s<<" ";// 输出十六进制，以空格分隔}return0;}

【运行结果】

0 00