UVa 740 Baudot Data Communication Code

题目描述Baudot\texttt{Baudot}Baudot码是一种早期数据通信中使用的编码每个字符用555个比特表示最多可编码323232个不同字符。为扩展容量该码使用上档Shift Up\texttt{Shift Up}Shift Up和下档Shift Down\texttt{Shift Down}Shift Down两种模式类似于打字机的大小写切换。给定完整的323232个下档字符和323232个上档字符以及若干条由0和1组成的消息每行一条长度不超过808080比特要求将每条消息按Baudot\texttt{Baudot}Baudot码解码为可读文本。初始状态默认为下档状态。遇到上档码11111后切换为上档遇到下档码11011后切换为下档。其他555位码组按当前模式查表输出对应字符。输入格式输入包含两部分。第一行包含323232个下档字符包括空格和移位字符的占位符第二行包含323232个上档字符。随后若干行每行一个由0和1组成的字符串表示一条消息。输入以文件结束终止。每条消息最长808080位初始状态为下档。输出格式对于每条消息输出一行解码后的文本。样例输入 T\*0 HNMLRGIPCVEDDSYFXAWJ UQK 59 %, )480::3$?#6!/-271( 100100110011000010011111101110001111101111101 001100001101111100100111111000010011000100011001101111100000111样例输出DIAL:911 NOV 5,8AM题目分析Baudot\texttt{Baudot}Baudot码的每条消息由连续的555位码组构成。两个特殊码组用于切换模式11111表示上档Shift Up\texttt{Shift Up}Shift Up11011表示下档Shift Down\texttt{Shift Down}Shift Down。其余码组根据当前模式从对应的323232字符表中查找并输出。初始模式为下档。输入行可能包含空格但由于消息由0和1组成直接读取即可。解题思路实现步骤如下步骤1\texttt{1}1. 读取两行字符串分别存储下档字符表downdowndown和上档字符表upupup长度均为323232。步骤2\texttt{2}2. 对每条消息设置状态变量isDowntrueisDown trueisDowntrue。从位置i0i 0i0开始每次取555位子串pieceline.substr(i,5)piece line.substr(i, 5)pieceline.substr(i,5)。步骤3\texttt{3}3. 若piecepiecepiece等于11011则设置isDowntrueisDown trueisDowntrue表示进入下档模式若等于11111则设置isDownfalseisDown falseisDownfalse表示进入上档模式否则将piecepiecepiece转换为整数indexindexindex二进制值根据isDownisDownisDown选择down[index]down[index]down[index]或up[index]up[index]up[index]输出对应字符。步骤4\texttt{4}4. 每处理完一条消息输出换行。代码实现// Baudot Data Communication Code// UVa ID: 740// Verdict: Accepted// Submission Date: 2016-11-30// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string down_characters,up_characters;getline(cin,down_characters);getline(cin,up_characters);string line;while(getline(cin,line)){inti0;boolis_downtrue;while(iline.length()){string pieceline.substr(i,5);if(piece11011)is_downtrue;elseif(piece11111)is_downfalse;else{bitset5indexer(piece);if(is_down)coutdown_characters[indexer.to_ulong()];elsecoutup_characters[indexer.to_ulong()];}i5;}cout\n;}return0;}总结本题模拟Baudot\texttt{Baudot}Baudot码解码过程核心是处理模式切换码组和按当前模式查表。利用bitset5\texttt{bitset5}bitset5将555位二进制字符串转换为整数索引简化转换。注意初始状态为下档且两个特殊码组仅切换状态而不输出字符。消息长度可能不是555的倍数但题目保证有效因此直接按每555位处理即可。该算法时间复杂度O(L)O(L)O(L)空间O(1)O(1)O(1)适用于短消息解码。