当前位置：首页 > news >正文

UVa 213 Message Decoding

news 2026/5/14 16:18:26

题目分析

本题是一种特殊的消息编码解码问题。编码方案包含两个部分：头部（header）和编码消息（message）。

头部是一个字符串，其中的每个字符按照特定顺序映射到二进制键（key）序列上。键序列的生成规则如下：

长度为111的键有111个：0
长度为222的键有333个：00、01、10
长度为333的键有777个：000、001、010、011、100、101、110
长度为nnn的键有2n−12^n - 12n−1个（排除全111的键）

键序列按长度递增、同长度内按二进制数值递增的顺序，依次映射到头部的每个字符。头部中可能出现重复字符，这会导致多个键映射到相同字符。

编码消息由若干个段（segment）组成：

每个段的前333个比特表示该段中键的二进制长度LLL（111到777）
随后是若干个长度为LLL的键，每个键对应头部的一个字符
段以LLL个连续的1作为结束标记
整个消息以000终止（表示长度为000的段）

消息中可能包含任意位置的换行符，需忽略。

解题思路

1. 建立键到索引的映射

由于键的最大长度为777，我们可以预先计算所有可能的键（除全111外）对应的索引值。索引从000开始，与头部字符的位置一一对应。这样在解码时，可以直接根据键字符串查找对应的头部字符。

2. 处理输入

每个数据集的第一行是头部字符串
后续若干行是编码消息（可能跨多行），直到遇到下一个头部或文件结束
需要特殊处理空行或只有换行符的情况

3. 解码过程

读取头部字符串
累积消息行到缓冲区，去除其中的换行符
循环处理消息：
- 读取前333位获取段长度LLL
- 若L=0L = 0L=0，消息结束，输出换行并开始下一个数据集
- 否则，继续读取长度为LLL的键
- 若遇到LLL个连续的1，表示该段结束，回到读取段长度的步骤
- 否则，根据键查找头部字符并输出

4. 注意事项

使用bitset或字符串处理生成键的二进制表示
缓冲区可能一次性包含多个段的内容，需要循环处理
输出格式：每个数据集的解码结果占一行，结果之间没有空行

代码实现

// Message Decoding// UVa ID: 213// Verdict: Accepted// Submission Date: 2016-04-28// UVa Run Time: 0.010s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 全局映射表：二进制键字符串 -> 对应的索引值（头部中的位置）map<string,int>indexer;intmain(){// 预处理所有可能的键及其对应的索引// 对于长度 length = 1 到 7// 每个长度下可能的键数量为 (2^length - 1)，排除全1for(inti=2,idx=0,length=1;length<8;i*=2,length++)for(intj=0;j<(i-1);j++){bitset<8>n(j);// 将整数 j 转为二进制// 取低 length 位作为键，存入映射表，索引递增indexer[n.to_string().substr(8-length,length)]=idx++;}string line,head,buffer;// 输入行、头部字符串、消息缓冲区boolheadReaded=false;// 是否已读头部boolsegmentEnded=false;// 当前段是否结束boolsegmentStartReaded=false;// 是否已读段长度intkeyLength;// 当前段的键长度while(getline(cin,line)){if(!headReaded){// 读取头部字符串head=line;headReaded=true;}else{// 将每一行追加到消息缓冲区（忽略换行符，已通过 getline 移除）buffer+=line;nextReading:// 跳转标签，用于段结束时继续处理if(!segmentStartReaded){// 缓冲区足够读取 3 位段长度时if(buffer.length()>=3){// 将前 3 位二进制转为整数，表示键长度keyLength=stoi(buffer.substr(0,3),NULL,2);if(keyLength==0){// 消息结束标志：000headReaded=false;// 准备读取下一个数据集的头部segmentStartReaded=false;buffer.clear();cout<<"\n";// 输出换行分隔不同数据集}else{// 移除已读的 3 位长度信息buffer.erase(0,3);segmentStartReaded=true;// 接下来开始读取段内键segmentEnded=false;}}}if(!segmentEnded){// 不断读取长度为 keyLength 的键，直到缓冲区不够while(buffer.length()>=keyLength){string key=buffer.substr(0,keyLength);if(key==string(keyLength,'1')){// 遇到全 1 的键，表示段结束segmentEnded=true;segmentStartReaded=false;buffer.erase(0,keyLength);// 移除结束标记gotonextReading;// 跳转读取下一个段的长度}else{// 普通键：通过映射表找到对应头部字符并输出cout<<head[indexer[key]];buffer.erase(0,keyLength);// 移除已处理的键}}}}}return0;}