题面解释：

题目要求对一段经过编码的二进制数据进行校验，数据由0个或多个编码单元组成。编码单元分为两种类型：简单编码单元和复杂编码单元。简单编码单元的TAG为0xF0，后面跟随4字节的值；复杂编码单元的TAG为0xF1，后面包含一个重复次数（1字节）、一个长度（4字节），以及指定字节数的值部分，这部分可以由0个或多个编码单元组成。输入为一行16进制表示的编码数据，输出解码后的总字节数或-1表示不合法。如果编码数据符合规则，计算解码后的总长度；否则，返回-1表示数据不合法。

思路:字符串模拟，递归

F0是普通编码，我们直接识别即可。

F1是复杂编码，它指示着后续的len长度的字节数据会重复rep次。而且我们发现这len长度的字节数据内同样可以蕴含F1编码。所以我们自然想到需要用递归来拆解这个编码。

对于每种编码，我们需要确保输入合法性，检查输入是否足够长以进行解析;检查各个部分是否是有效的十六进制数。

题解

我们需要解码一段经过编码的二进制数据，数据由多个编码单元组成，这些编码单元有两种类型：简单编码单元和复杂编码单元。我们的目标是验证这些编码单元的格式是否符合规定，并计算出解码后的数据长度。

编码单元解析

1. 简单编码单元 (F0)：

   • 结构：以0xF0开头，后面跟随4个字节的值。
   • 长度：每个简单编码单元解码后贡献4字节。
   • 合法性检查：
     • 确保后续有足够的字节（至少5字节）。
     • 检查后续4字节是否都是有效的十六进制数。

2. 复杂编码单元 (F1)：

   • 结构：以0xF1开头，后面包含：
     • 重复次数（1字节）
     • 长度（4字节，表示后续字节的数量）
     • 值部分，包含0个或多个编码单元，总长度必须等于指定的字节数。
   • 合法性检查：
     • 确保有足够的字节（至少6字节）。
     • 检查重复次数和长度是否合理（尤其是后续的内容是否满足长度要求）。
     • 对值部分递归调用解码函数，以处理其中可能嵌套的编码单元。

代码实现

代码实现中，我们使用递归来解析复杂编码单元，并逐层累加解码后的长度。以下是代码的主要逻辑说明：

• 检查十六进制合法性：定义了一个checkHex函数，用于检查字符串是否为合法的十六进制数。

• 解码函数：decode函数负责解析输入数据：

  • 通过索引遍历输入数据，并根据当前的TAG来判断是简单编码单元还是复杂编码单元。
  • 递归地处理复杂编码单元的值部分，确保正确计算出总长度。

• 主函数：从标准输入读取数据，解析并存入一个字符串数组，然后调用解码函数。

具体实现见代码注释

代码

java

import java.util.Scanner;

public class Main {
    static String[] data;
    static int inf = (int) 1e9;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 特判：如果没有输入内容，直接输出 0 并结束程序
        if (!sc.hasNextLine()) {
            System.out.println(0);
            return;
        }

        String input = sc.nextLine().trim();  // 读取输入并去除首尾空格

        // 特判：如果输入为空字符串，直接输出 0
        if (input.isEmpty()) {
            System.out.println(0);
            return;
        }

        data = input.split(" ");  // 将输入按空格分割为字符串数组
        int n = data.length;  // 获取数组长度
        int res = decode(0, n);  // 从索引 0 开始解码
        if (res <= 0) {
            res = -1;  // 如果解码结果小于等于 0，返回 -1
        }
        System.out.println(res);  // 输出结果
    }

    // 检查字符串是否为合法的十六进制数
    static boolean checkHex(String s) {
        return s.matches("[0-9A-Fa-f]+");  // 使用正则表达式检查
    }

    // 解码函数，递归解析编码
    static int decode(int idx, int n) {
        if (idx >= n) return 0;  // 如果索引超出范围，返回 0

        if (data[idx].equals("F0")) {  // 处理 F0 编码
            if (idx + 4 >= n) return -inf;  // 检查长度是否足够
            for (int i = 1; i <= 4; i++) {  // 检查是否为有效的十六进制数
                if (!checkHex(data[idx + i])) return -inf;
            }
            return 4 + decode(idx + 5, n);  // 返回长度 4 加上递归解码结果
        } else if (data[idx].equals("F1")) {  // 处理 F1 编码
            if (idx + 5 >= n) return -inf;  // 检查长度是否足够
            for (int i = 1; i <= 5; i++) {  // 检查是否为有效的十六进制数
                if (!checkHex(data[idx + i])) return -inf;
            }
            int rep = Integer.parseInt(data[idx + 1], 16);  // 解析重复次数
            int length = 0;  // 初始化长度
            for (int i = 2; i <= 5; i++) {  // 计算长度
                length = length * 16 + Integer.parseInt(data[idx + i], 16);
            }
            if (idx + 5 + length >= n) return -inf;  // 检查长度是否足够
            return rep * decode(idx + 6, idx + 6 + length) + decode(idx + 6 + length, n);  // 递归解码
        }
        return -inf;  // 返回无效值
    }
}

python

inf = 10**9  # 定义无效值

# 检查字符串是否为合法的十六进制数
def check_hex(s):
    valid = "0123456789ABCDEFabcdef"
    for c in s:
        if c not in valid:
            return False  # 如果有字符不合法，返回 False
    return True  # 所有字符合法

# 解码函数，递归解析编码
def decode(idx, n):
    if idx >= n:
        return 0  # 如果索引超出范围，返回 0
    if data[idx] == "F0":  # 处理 F0 编码
        if idx + 4 >= n:
            return -inf  # 检查长度是否足够
        for i in range(1, 5):  # 检查是否为有效的十六进制数
            if not check_hex(data[idx + i]):
                return -inf  # 如果不合法，返回无效值
        return 4 + decode(idx + 5, n)  # 返回长度 4 加上递归解码结果
    elif data[idx] == "F1":  # 处理 F1 编码
        if idx + 5 >= n:
            return -inf  # 检查长度是否足够
        for i in range(1, 6):  # 检查是否为有效的十六进制数
            if not check_hex(data[idx + i]):
                return -inf  # 如果不合法，返回无效值
        rep = int(data[idx + 1], 16)  # 解析重复次数
        length = 0  # 初始化长度
        for i in range(2, 6):  # 计算长度
            length = length * 16 + int(data[idx + i], 16)
        if idx + 5 + length >= n:
            return -inf  # 检查长度是否足够
        return rep * decode(idx + 6, idx + 6 + length) + decode(idx + 6 + length, n)  # 递归解码
    return -inf  # 返回无效值

try:
    data = input().split()  # 读取输入并分割成字符串列表
    n = len(data)  # 获取列表长度
except EOFError:
    print(0)  # 如果捕获到 EOFError，直接输出 0
    exit(0)

# 特判：如果输入为空字符串，直接输出0
if n == 0:
    print(0)
else:
    res = decode(0, n)  # 从索引 0 开始解码
    if res <= 0:
        res = -1  # 如果解码结果小于等于 0，返回 -1
    print(res)  # 输出结果

cpp

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int inf = 1e9;  // 定义无效值
vector<string> inputData;  // 存储输入数据

// 检查字符串是否为合法的十六进制数
bool checkHex(const string &s) {
    for (char c : s) {
        if (!isdigit(c) && (c < 'A' || c > 'F') && (c < 'a' || c > 'f')) {
            return false;  // 检查每个字符是否合法
        }
    }
    return true;  // 所有字符合法
}

// 解码函数，递归解析编码
int decode(int idx, int n) {
    if (idx >= n) return 0;  // 如果索引超出范围，返回 0

    if (inputData[idx] == "F0") {  // 处理 F0 编码
        if (idx + 4 >= n) return -inf;  // 检查长度是否足够
        for (int i = 1; i <= 4; i++) {  // 检查是否为有效的十六进制数
            if (!checkHex(inputData[idx + i])) return -inf;
        }
        return 4 + decode(idx + 5, n);  // 返回长度 4 加上递归解码结果
    } else if (inputData[idx] == "F1") {  // 处理 F1 编码
        if (idx + 5 >= n) return -inf;  // 检查长度是否足够
        for (int i = 1; i <= 5; i++) {  // 检查是否为有效的十六进制数
            if (!checkHex(inputData[idx + i])) return -inf;
        }
        int rep = stoi(inputData[idx + 1], nullptr, 16);  // 解析重复次数
        int length = 0;  // 初始化长度
        for (int i = 2; i <= 5; i++) {  // 计算长度
            length = length * 16 + stoi(inputData[idx + i], nullptr, 16);
        }
        if (idx + 6 + length > n) return -inf;  // 检查长度是否足够
        return rep * decode(idx + 6, idx + 6 + length) + decode(idx + 6 + length, n);  // 递归解码
    }
    return -inf;  // 返回无效值
}

int main() {
    string line;
    getline(cin, line);  // 读取一行输入

    // 特判：如果输入为空字符串，直接输出0
    if (line.empty()) {
        cout << 0 << endl;
        return 0;
    }

    stringstream ss(line);
    string s;
    while (ss >> s) {  // 分割输入并存入数据数组
        inputData.push_back(s);
    }

    int res = decode(0, inputData.size());  // 从索引 0 开始解码
    if (res <= 0) {
        res = -1;  // 如果解码结果小于等于 0，返回 -1
    }
    cout << res << endl;  // 输出结果
    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

指定有一段经过编码的二进制数据，数据由0个或多个"编码单元"组成。

编码单元“的编码方式存在如下两种:

1.简单编码单元如下所示，其中:

• $TAG$所占长度须为$1$字节，其值须为$0×F0$

• $SINGLE-VALUE$的长度固定为$4$字节

2.复杂编码单元如下所示，其中:

• $TAG$所占长度须为$1$字节，其值须为$0×F1$

• $REPEAT$所占长度固定为$1$字节，用于指示值在解码后消息中重复的次数

• $LEN$所占长度固定为$4$字节，用于指示值的字节数，$LEN$使用大端序表示

• 值部分**必须由$0$个或多个“编码单元"**组成，且长度必须为$LEN$字段所指示的字节数

编码后的数据必须完全符合上述两个原则，不允许有任何冗余的字节，请根据上述规则对一段编码后的数据进行校验，如果完全符合上述约束则输出解码后的长度，否则输出$-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

输出

8

说明

该码流存在一个复杂编码单元，其中包含一个简单编码单元(内容$4$字节)，复杂编码单元的重复数为$2$，所以解码后的总长度为$8$字节

样例2

输入

F1 01 00 00 00 04 F0 01 05

输出

-1

说明

第一个编码单元是复杂编码单元，重复数为$1$，长度为$4$，但是长度后的内容仅有$3$字节，码流不合法，返回$-1$

样例3

输入

F1 01 00 00 00 06 F0 00 00 00 03 03 03

输出

-1

说明

第一个编码单元为复杂编码单元，重复数为$1$、长度为$6$，

其中的内容从第一个字节开始为一个简单编码单元，

但简单编码单元后存在数据 $03$ $03$ 既不属于简单单元，

也不属于复杂编码单元，为冗余数据，整体数据不合法、应输出$-1$