刷题笔记合集🔗

题目描述

两端通过TLV格式的报文来通信，现在收到对端的一个TLV格式的消息包，要求生成匹配后的(tag, length, valueOffset)列表。

具体要求如下:

1. 消息包中多组tag、length、value紧密排列
   • tag和length各占1字节(uint8_t)
   • value所占字节数等于length的值
2. 需要填充每个tag对应的length和valueOffset值
   • valueOffset为value在原消息包中的起始偏移量(从0开始,以字节为单位)
   • 若tag匹配失败,则length和valueOffset都为0
3. tag值按升序排列且不重复
4. 消息包尾部可能不完整,不完整的TLV需丢弃

输入格式

第一行: 一个字符串,代表收到的消息包(长度≤10000)

• 使用十六进制文本格式(字母大写)
• 如0F04ABABABAB代表一组TLV:
  • 0F: tag值为15
  • 04: length值为4字节
  • ABABABAB: 4字节的value
• TLV紧密排列,无分隔符

第二行: 需要匹配的tag数量n (0 < n < 1000)

后面n行: n个tag值(十进制表示),递增排列

输出格式

n行匹配结果,每行两个数字:

• 第一个数字表示length
• 第二个数字表示valueOffset
• 用空格分隔

样例输入1

0F04ABABABAB
1
15

样例输出1

4 2

样例说明1

• tag 15(0F)对应数据长度为4
• value从第3个字节开始,偏移量为2

样例输入2

0F04ABABABAB1001FF
2
15
17

样例输出2

4 2
0 0

样例说明2

第二个tag 17匹配失败,输出0 0

题目解析

本题的关键点在于:

1. TLV格式解析

   • tag: 2位16进制 = 1字节
   • length: 2位16进制 = 1字节
   • value: length*2位16进制 = length字节

2. 偏移量计算

   • 字节为单位
   • value起始位置 = (tag+length位置+1)/2
   • 需要考虑16进制字符到字节的转换

3. 边界处理

   • 检查消息包完整性
   • 处理tag匹配失败
   • 处理不完整TLV

实现思路:

1. 遍历消息包,解析每组TLV
2. 计算并记录length和valueOffset
3. 匹配目标tag并输出结果

时间复杂度: O(n)，其中n是消息包长度

参考代码

def solve():
    try:
        # 读取输入
        msg = input()
        n = int(input())
        tags = [int(input()) for _ in range(n)]
        
        # 解析TLV并存储
        tag_info = {}
        i = 0
        while i + 3 < len(msg):
            # 解析tag和length
            tag = int(msg[i:i+2], 16)
            length = int(msg[i+2:i+4], 16)
            value_offset = (i + 5) // 2
            
            # 检查value是否完整
            value_end = i + 4 + length * 2
            if value_end > len(msg):
                break
                
            # 记录tag信息
            tag_info[tag] = (length, value_offset)
            
            # 移动到下一组TLV
            i = value_end
            
        # 输出结果
        for tag in tags:
            if tag in tag_info:
                length, offset = tag_info[tag]
                print(f"{length} {offset}")
            else:
                print("0 0")
                
    except:
        ret