時間限制:C/C++ 1000MS,其他語言 2000MS
內存限制:C/C++ 256MB,其他語言 512MB
難度:困難
內存限制:C/C++ 256MB,其他語言 512MB
難度:困難
數據解碼
指定有一段經過編碼的二進制數據,數據由0個或多個"編碼單元"組成。"編碼單元"的編碼方式存在如下兩種:
1簡單編碼單元如下所示,其中:
- TAG所占長度須為1字節,其值須為0xF0
- SINGLE-VALUE的長度定為4字節
2.復雜編碼單元如下所示,其中:
- TAG所占長度須為1字節,其值須為0xF1
- REPEAT所占長度固定為1字節,用于指示值在解碼后消息中重復的次數
- LEN所占長度固定為4字節,用于指示值的字節數,LEN使用大端序表示
- 值部分必須由0個或多個"編碼單元"組成,且長度必須為LEN字設所指示的字節數
編碼后的數據必須完全符合上述兩個原則,不允許有任何冗余的字節,請構造符合上述規則的10個編碼:
請根據上述規則對一段編碼后的數據進行校驗,如果完全符合上述約束則輸出解碼后的長度,否則輸出-1
輸入描述
輸入一行編碼后的二進制數據,按字節16進制表示,如
F0 00 08 09 00
表示一串5字節的編碼后數據
輸入的字節數n,0<=n<=100000
輸出描述
輸出解碼后的值的字節數,不符合約束返回-1
用例輸入 1?
F1 02 00 00 00 05 F0 01 02 03 04
用例輸出 1?
8
用例輸入 2?
F1 01 00 00 00 04 F0 01 05
用例輸出 2?
-1
提示
樣例1解釋:該碼流存在一個復雜編碼單元,其中包含一個簡單編碼單元(內容4字節),復雜編碼單元的重復數為2,所以解碼后的總長度為8字節
樣例2解釋:第一個編碼單元為復雜編碼單元,重復數為1,長度為6,其中的內容從第一個字節開始為一個簡單編碼單元,但簡單編碼單元后存在數據0303既不屬于簡單編碼單元,也不屬于復雜編碼單元,為冗余數據,整體數據不合法,應輸出-1
#include <iostream>
#include <vector>
#include <cstdint>using namespace std;// Helper function to parse a single encoding unit
pair<int, int> parseUnit(const vector<uint8_t>& data, int index) {if (index >= data.size()) {return {-1, -1}; // Invalid input}uint8_t tag = data[index];index++;if (tag == 0xF0) {// Simple encoding unit: 1 byte TAG + 4 bytes SINGLE-VALUEif (index + 4 > data.size()) {return {-1, -1}; // Not enough bytes for SIMPLE-VALUE}return {index + 4, 4}; // Move past the SIMPLE-VALUE and return decoded length} else if (tag == 0xF1) {// Complex encoding unit: 1 byte TAG + 1 byte REPEAT + 4 bytes LEN + LEN bytes contentif (index + 5 > data.size()) {return {-1, -1}; // Not enough bytes for REPEAT and LEN}uint8_t repeat = data[index];index++;// Read LEN (4 bytes, big-endian)uint32_t len = 0;for (int i = 0; i < 4; ++i) {len = (len << 8) | data[index++];}// Check if we have enough bytes for the contentif (index + len > data.size()) {return {-1, -1}; // Not enough bytes for the content}// Parse the content recursivelyint contentStart = index;int totalDecoded = 0;while (index < contentStart + len) {auto [newIndex, decodedLen] = parseUnit(data, index);if (newIndex == -1) {return {-1, -1}; // Invalid content}index = newIndex;totalDecoded += decodedLen;}// Ensure no extra bytes in the contentif (index != contentStart + len) {return {-1, -1}; // Extra bytes found}return {index, totalDecoded * repeat};} else {// Invalid TAGreturn {-1, -1};}
}// Main function to decode the length
int decodeLength(const vector<uint8_t>& data) {auto [index, decodedLen] = parseUnit(data, 0);// Ensure all bytes are consumedif (index == static_cast<int>(data.size())) {return decodedLen;} else {return -1; // Redundant bytes found}
}// Helper function to convert hex string to byte array
vector<uint8_t> hexToBytes(const string& hex) {vector<uint8_t> bytes;for (size_t i = 0; i < hex.length(); i += 2) {string byteString = hex.substr(i, 2);uint8_t byte = static_cast<uint8_t>(stoul(byteString, nullptr, 16));bytes.push_back(byte);}return bytes;
}int main() {string hexInput;getline(cin, hexInput);// Remove spaces from the inputstring cleanedInput;for (char c : hexInput) {if (c != ' ') {cleanedInput += c;}}// Convert hex string to byte arrayvector<uint8_t> data = hexToBytes(cleanedInput);// Decode the lengthint result = decodeLength(data);cout << result << endl;return 0;
}