B3870 [GESP202309 四级] 变长编码题解

· · 题解

本题主要是模拟，详细函数用法以及做法都在代码里

#include<bits/stdc++.h>
using namespace std;
string a;
void str_To_Hex(string str){
    long long sum=0;
    for(int i=str.size()-1,k=1;i>=0;i--,k*=2){
        sum+=(str[i]-'0')*k;//按位增加
    }
    printf("%02X ",sum);
}//即字符串类型的二进制转换成十六进制数并输出
int main(){
    long long n,k;//注意，题目输入为1e18，必须为长整型或无符号长整型
    cin>>n;//输入
    if(n==0){
        cout<<"00";
        return 0;
    }//特判0的情况，简化步骤并使其不会出现错误
    k=n;
    while(k){
        a.push_back(k%2+'0');//将转换出的数字放在string串后面，其效率比insert更高
        k/=2;
    }//将n转换成2进制串
    reverse(a.begin(),a.end());//翻转，使a在后面的操作中更好找到最高位。
    //reverse函数，是对任何类型的数组进行翻转的一个函数。
    //通常用法为 reverse(a.begin(),a.end()) 或 reverse(a,a+n);
    while(a.size()%7) a='0'+a;//不足7bit的转在高位填补'0'，此代码比insert更快
    a.insert(a.begin(),'0');//最后一组在最高位填'0',使其成为8bit组，注意，在二进制串中，通常高位是第一位
    for(int i=8;i<a.size()-1;i+=7){//从倒数第二个组开始，直至第一个组结束
        a.insert(a.begin()+i,'1');//其他7bit组在最高位上填'1',使其成为8bit组
        i++;//增加一个元素过后，需要将i移动到添加的元素的后面
    }
    for(int i=a.size();i>0;i-=8){
        int st=i-8;
        string str;
        str=a.substr(st,8);//分成8bit每组
        //substr函数，是string类型的一种函数。
        //通常用于截取子串，用法为a.substr(begin,num)。
        //表示为从begin开始，截取共num个元素，并将其整合为string类型，返回。
        str_To_Hex(str);//转换并输出
    }
    return 0;
}