做衣服外单网站网络项目免费的资源网

大家好，我是莫小特。
这篇文章给大家分享 GESP 四级 2023 年 9 月编程题第 2 题：变长编码。

题目链接

洛谷链接：B3870 变长编码

一、完成输入

根据输入格式的描述，输入一个正整数 N，数据范围：$0\le N\le 10^{18}$，因此使用 long long 类型。

long long N;
cin>>N;

输入完成后，我们来分析题意，解决算法。

二、分析题意

根据题目要求，输出一行，输出 N 对应的变长编码的每个字节，每个字节要用 2 位十六进制表示。

所以题目的意思就是要将数字 N 转换成变长编码。

根据题目的描述，要对给定的整数转变成二进制形式。

所以我们要对输入的整数进行处理，转换成二进制的形式。

需要定义一个数组，全部初始化为 0，元素个数我们先定义限制在 $10^5$。

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;j<i;j++)
{b[j]=a[i-j];
}

将 b 数组输出，测试转换二进制是否正确。

for(int k=1;k<i;k++)
{cout<<b[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};