《古籍翻译》题解

阮行止 · 2022-03-13 21:13:09 · 题解

朴素做法是写一个高精度，对整个数做进制转换。

有更好的做法。注意到每 4 个八进制码包含 12 个 bit 的信息，即对应 3 个十六进制码。故将八进制串每 4 个数位打包，转成十六进制。复杂度 \mathcal{O}(|s|).

例子：1572061125 打包为 [15] [7206] [1125]，这三个包在十进制下分别是 13, 3718, 597。转为十六进制，即 [d] [e86] [255]，输出 de86255。

有几个细节需要注意：

• 从后往前打包，而非从前往后。从样例中可以看出这一点。
• 除了第一个包之外，输出十六进制时，需要补上前导 0。

参考代码：

#include <bits/stdc++.h>
using namespace std;

char buffer[100005];

int octToInt(int l, int r) {
    int n = 0;
    for(int i=l; i<r; i++)
        n = n * 8 + buffer[i] - '0';
    return n;
}

void work(int len) {
    int low = max(0, len - 4);
    int n = octToInt(low, len);

    if(low) {
        work(low);
        printf("%03x", n);
    } else {
        printf("%x", n);
    }
}

int main() {
    cin >> buffer;
    work(strlen(buffer));

    return 0;
}