题解：P14602 [NWRRC 2025] Compact Encoding

· · 题解

题目理解

  1. 将整数的二进制表示按 7 位一组进行分割。
  2. 每个字节的最高位(第8位)表示是否还有后续字节。
    • 1：后面还有更多字节。
    • 0：这是最后一个字节。
  3. 第一个字节包含原数的最高有效位。
  4. 不能以 128（二进制 10000000）开头。

做法

  1. 特殊情况处理：当输入为 0 时，直接输出 0。
  2. 7 位分组：将整数的二进制表示按 7 位一组从低位到高位分割。
  3. 大端序处理：由于编码要求大端序，需要反转字节顺序。
  4. 设置继续标志：非最后一个字节的最高位置 1，最后一个字节的最高位置 0。

Code

#include <bits/stdc++.h>
using namespace std;
unsigned int n;
vector<unsigned int>b;
int main(){
    cin>>n;
    if(n==0){//特判 n=0 
        cout<<0;
        return 0;
    }
    while(n>0){
        b.push_back(n&0x7F);//从低位开始，每次取 7 位  
        n>>=7;
    }
    for(int i=b.size()-1;i>=0;i--){
        if(i>0)cout<<(b[i]|0x80)<<" ";//最后一个字节，最高位置设为 1 
        else cout<<b[i]<<" ";
    }
}