网站建设昆明网络公司,seo入门书籍推荐,免费制作个人网站,站长平台验证网站大家好，我是莫小特。 这篇文章给大家分享 GESP 四级 2023 年 9 月编程题第 2 题：变长编码。
题目链接
洛谷链接：B3870 变长编码 一、完成输入
根据输入格式的描述，输入一个正整数 N，数据范围： 0 ≤ N ≤ 10 18 0 \le N \le 10^{18} 0≤N≤1018，因此使用 long long 类…
大家好，我是莫小特。 这篇文章给大家分享 GESP 四级 2023 年 9 月编程题第 2 题：变长编码。
题目链接
洛谷链接：B3870 变长编码 一、完成输入
根据输入格式的描述，输入一个正整数 N，数据范围： 0 ≤ N ≤ 10 18 0 \le N \le 10^{18} 0≤N≤1018，因此使用 long long 类型。
long long N;
cinN;输入完成后，我们来分析题意，解决算法。
二、分析题意
根据题目要求，输出一行，输出 N 对应的变长编码的每个字节，每个字节要用 2 位十六进制表示。
所以题目的意思就是要将数字 N 转换成变长编码。
根据题目的描述，要对给定的整数转变成二进制形式。
所以我们要对输入的整数进行处理，转换成二进制的形式。
需要定义一个数组，全部初始化为 0，元素个数我们先定义限制在 10 5 10^5 105。
const int num=1e5+10;
int a[num]={0};//初始化数组对输入的数据进行二进制变化，将转变后的二进制存储数组中。
具体的操作如图示，数组的下标从 1 开始，每次记录。 int i=1;
while(N!=0)
{a[i]=N%2;//二进制的最高位N/=2;i++;//记录下一位
}但由于二进制是倒序，原本记录在数组中的高位要变成低位，如图示，原数组下标和二进制下标的规则是两个下标相加等于一个相同的数。 因此需要一个新的变量来存储正确的二进制数据，根据之前的规律，两个下标相加等于相同的数，也就是 i。
int b[num]={0};
for(int j=1;ji;j++)
{b[j]=a[i-j];
}将 b 数组输出，测试转换二进制是否正确。
for(int k=1;ki;k++)
{coutb[k];
}数据正确，证明二进制转换正确。 二进制完成后，来到第二步，将二进制数从低位到高位切分为 7 位。
因此需要在 b 数组中倒序访问 7 个，单独存储在一个数组中，考虑到会有多组数据，因要定义一个二维数组。
int len=i-1; //二进制位个数
int now=len; //从低位开始处理由于编码时是从最低位开始，每7位一组，所以我们需要从 b[len] 开始往前读，now 变量就是当前正在处理位的下标，从后往前。
使用二维数组 group[g][j] 来存储每一组的 7 位，外层下标 g 表示第几组（从 1 开始），内层下标 j 表示这一组中的第几位（二进制位）
注意要先初始化为全 0。
int group[100][10] = {0};
