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

知识点：进制转换、位运算、编码模拟。

解题思路

把数按128进制从低到高取组，每组保留7位；若后面仍有组，将当前字节最高位设1。每个字节以两位十六进制输出。

为什么正确

低7位依次保存所有原始二进制位，最高位准确指示是否还有后续字节，构成题目变长编码。

易错点

低组先输出；n=0也必须输出00，所以用do-while；字节间用空格。

复杂度

时间O(log128 n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unsigned long long n;
    cin>>n;
    string h="0123456789ABCDEF";
    bool first=true;
    do {
        int b=n%128;
        n/=128;
        if(n)b+=128;
        if(!first)cout<<" ";
        first=false;
        cout<<h[b/16]<<h[b%16];
    }
    while(n);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。