CSP 202305-3 解压缩

黎 浩然/ 14 8 月, 2023/ 算法/ALGORITHMS/ 0 comments

Java：80/100 (内存超限)

import java.util.Scanner;

public class Main {

    public static String hexByte2binByte(String hexString, int index) {
        StringBuilder binByte = new StringBuilder(Integer.toBinaryString(Integer.parseInt(hexString.substring(index, index + 2), 16)));
        while (binByte.length() < 8) {
            binByte.insert(0, "0");
        }
        return binByte.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder compressedData = new StringBuilder();
        int compressDataLength = scanner.nextInt();
        while (compressedData.length() < compressDataLength * 2) {
            compressedData.append(scanner.next());
        }

        int o, l, i, length; // 避免内存重复分配
        int power = 0;
        int index = 0; // 当前处理到的压缩数据的索引
        int originalDataLength = 0; //原始数据长度
        String binByte = null; // 避免内存重复分配
        StringBuilder originalData = new StringBuilder();

        // 引导区
        for (; index < compressedData.length() && (index == 0 || binByte.charAt(0) != '0'); power += 1, index += 2) {
            binByte = hexByte2binByte(compressedData.toString(), index);
            originalDataLength += Integer.parseInt(binByte.substring(1), 2) * Math.pow(128, power);
        }

        while (index < compressedData.length()) {
            binByte = hexByte2binByte(compressedData.toString(), index);
            if (binByte.charAt(6) == '0' && binByte.charAt(7) == '0') {
                length = Integer.parseInt(binByte.substring(0, 6), 2); // 元素长度 (字节数量)
                if (length < 60) {
                    originalData.append(compressedData.substring(index + 2, index + 2 + 2 * (length + 1)));
                    index += (2 + 2 * (length + 1));
                } else {
                    power = length - 60;
                    length = Integer.parseInt(compressedData.substring(index + 2, index + 4), 16) + 1;
                    for (i = 0; i < power; i++) {
                        length += Integer.parseInt(compressedData.substring(index + 4 + 2 * i, index + 6 + 2 * i), 16) * Math.pow(256, i + 1);
                    }
                    originalData.append(compressedData.substring(index + 4 + 2 * power,index + 4 + 2 * power + 2 * length));
                    index += (4 + 2 * power + 2 * length);
                }
            } else if (binByte.charAt(6) == '0' && binByte.charAt(7) == '1') {
                o = Integer.parseInt(binByte.substring(0, 3), 2) * 256 + Integer.parseInt(compressedData.substring(index + 2, index + 4), 16);
                l = Integer.parseInt(binByte.substring(3, 6), 2) + 4;
                i = originalData.length() - 2 * o;
                for (int j = 0; j < 2 * l; j += 1, i += 1) {
                    originalData.append(originalData.charAt(i));
                }
                index += 4;
            } else if (binByte.charAt(6) == '1' && binByte.charAt(7) == '0') {
                o = Integer.parseInt(compressedData.substring(index + 4, index + 6), 16) * 256 + Integer.parseInt(compressedData.substring(index + 2, index + 4), 16);
                l = Integer.parseInt(binByte.substring(0, 6), 2) + 1;
                i = originalData.length() - 2 * o;
                for (int j = 0; j < 2 * l; j += 1, i += 1) {
                    originalData.append(originalData.charAt(i));
                }
                index += 6;
            }
        }

        for (index = 0; index < originalDataLength * 2; index += 16) {
            System.out.println(originalData.substring(index, Math.min(index + 16, originalDataLength * 2)));
        }
    }
}

C++：100/100

#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <bitset>

std::string hexByte2binByte(const std::string& hexString, int index) {
    int val;
    std::stringstream ss;

    ss << std::hex << hexString.substr(index, 2);
    ss >> val;
    return std::bitset<8>(val).to_string();
}

int main() {

    int o, l, i, length;
    int power = 0;
    int index = 0;
    int compressDataLength = 0;
    int originalDataLength = 0;
    std::string tmp;
    std::string binByte;
    std::string originalData;
    std::string compressedData;

    std::cin >> compressDataLength;
    while (compressedData.length() < compressDataLength * 2) {
        std::cin >> tmp;
        compressedData.append(tmp);
    }

    for (; index < compressedData.length() && (index == 0 || binByte[0] != '0'); power += 1, index += 2) {
        binByte = hexByte2binByte(compressedData, index);
        originalDataLength += std::stoi(binByte.substr(1), nullptr, 2) * (int)std::pow(128, power);
    }

    while (index < compressedData.length()) {
        binByte = hexByte2binByte(compressedData, index);
        if (binByte[6] == '0' && binByte[7] == '0') {
            length = std::stoi(binByte.substr(0, 6), nullptr, 2);
            if (length < 60) {
                originalData.append(compressedData.substr(index + 2, 2 * (length + 1)));
                index += (2 + 2 * (length + 1));
            } else {
                power = length - 60;
                std::stringstream ss;
                ss << std::hex << compressedData.substr(index + 2, 2);
                ss >> length;
                length += 1;

                for (i = 0; i < power; i++) {
                    std::stringstream sst;
                    sst << std::hex << compressedData.substr(index + 4 + 2 * i, 2);
                    int val;
                    sst >> val;
                    length += val * (int)std::pow(256, i + 1);
                }
                originalData.append(compressedData.substr(index + 4 + 2 * power, 2 * length));
                index += (4 + 2 * power + 2 * length);
            }
        } else if (binByte[6] == '0' && binByte[7] == '1') {
            o = std::stoi(binByte.substr(0, 3), nullptr, 2) * 256 + std::stoi(compressedData.substr(index + 2, 2), nullptr, 16);
            l = std::stoi(binByte.substr(3, 3), nullptr, 2) + 4;
            i = (int)(originalData.length() - 2 * o);
            for (int j = 0; j < 2 * l; j += 1, i += 1) {
                originalData += originalData[i];
            }
            index += 4;
        } else if (binByte[6] == '1' && binByte[7] == '0') {
            o = std::stoi(compressedData.substr(index + 4, 2), nullptr, 16) * 256 + std::stoi(compressedData.substr(index + 2, 2), nullptr, 16);
            l = std::stoi(binByte.substr(0, 6), nullptr, 2) + 1;
            i = (int)(originalData.length() - 2 * o);
            for (int j = 0; j < 2 * l; j += 1, i += 1) {
                originalData += originalData[i];
            }
            index += 6;
        }
    }

    for (index = 0; index < originalDataLength * 2; index += 16) {
        std::cout << originalData.substr(index, std::min(16, originalDataLength * 2 - index)) << std::endl;
    }

    return 0;
}