UVa 730 Morse Code Generation

题目描述本题要求根据给定的摩尔斯电码表和传输速度模拟报文的发送过程输出每个字符对应的发射机开启/关闭时间毫秒。发送规则遵循摩尔斯电码的时序定义并按照速度wpm\texttt{wpm}wpm调整时间间隔。输入格式输入文件包含两部分映射表若干行每行一个字符大写字母或数字及其摩尔斯码表示由点.和划-组成直到出现单独一行仅包含的标记行结束。数据集一个或多个数据集每个数据集以单独一行开始第一个已用于结束映射表但后续每个数据集也以开头。接着一行是一个整数www表示传输速度words‑per‑minute\texttt{words‑per‑minute}words‑per‑minute。之后是多行报文报文可能包含大小写字母、数字和空格。报文行之间的换行符除最后一行外视为单词间隔。输入以文件结束EOF\texttt{EOF}EOF终止。输出格式对于每个数据集输出报文的一个副本每个有效字符仅限A–Z和0–9占一行。每行以该字符开头随后输出该字符摩尔斯码中每个符号的开启时间毫秒及紧随其后的关闭时间即字符内间隔开启时间后跟一个字符S关闭时间后跟一个字符N。每个时间前后各有一个空格。在所有符号输出完毕后输出该字符后的间隔时间字符间间隔或单词间间隔并跟N。若该字符后紧跟一个空格即单词分隔则需要在下一行输出行首两个空格然后输出单词间间隔时间和N。两个数据集的输出之间用一个空行分隔。所有时间值均为整数四舍五入。样例输入A .- B -... D -.. G --. O --- Y -.-- 5 A BAD BOY 13 A good boy输出A 115 S 300 N 346 S 300 N 900 N 2700 N B 346 S 300 N 115 S 300 N 115 S 300 N 115 S 300 N 900 N A 115 S 300 N 346 S 300 N 900 N D 346 S 300 N 115 S 300 N 115 S 300 N 900 N 2700 N B 346 S 300 N 115 S 300 N 115 S 300 N 115 S 300 N 900 N O 346 S 300 N 346 S 300 N 346 S 300 N 900 N Y 346 S 300 N 115 S 300 N 346 S 300 N 346 S 300 N 900 N A 115 S 115 N 346 S 115 N 346 N 1038 N G 346 S 115 N 346 S 115 N 115 S 115 N 346 N O 346 S 115 N 346 S 115 N 346 S 115 N 346 N O 346 S 115 N 346 S 115 N 346 S 115 N 346 N D 346 S 115 N 115 S 115 N 115 S 115 N 346 N 1038 N B 346 S 115 N 115 S 115 N 115 S 115 N 115 S 115 N 346 N O 346 S 115 N 346 S 115 N 346 S 115 N 346 N Y 346 S 115 N 115 S 115 N 346 S 115 N 346 S 115 N 346 N题目分析摩尔斯码的时序定义以“点”为基本单位。一个“划”的长度为三个点。字符内符号之间的间隔点或划之后至少为一个点的长度字符间间隔为三个点单词间间隔为九个点。在131313wpm\texttt{wpm}wpm的基准速度下每分钟传送13×56513 \times 5 6513×565个字符每个字符平均888个点长度故每分钟共有65×852065 \times 8 52065×8520个点单位。因此基准点长为baseDot60000520≈115.3846 ms \textit{baseDot} \frac{60000}{520} \approx 115.3846 \text{ ms}baseDot52060000​≈115.3846ms当速度低于131313wpm\texttt{wpm}wpm时点信号本身的持续时间保持不变仍为基准点长而通过增大字符内间隔来降低整体传送速度当速度高于或等于131313wpm\texttt{wpm}wpm时点信号时长和字符内间隔均随速度同步变化。具体地若速度为wwwwpm\texttt{wpm}wpm则每分钟有w×5×840ww \times 5 \times 8 40ww×5×840w个点单位因此点信号时长高速时为dot6000040w ms \textit{dot} \frac{60000}{40w} \text{ ms}dot40w60000​ms对于低速w13w 13w13点信号时长固定为baseDot\textit{baseDot}baseDot而字符内间隔则为intra6000040w ms \textit{intra} \frac{60000}{40w} \text{ ms}intra40w60000​ms注意此时intrabaseDot\textit{intra} \textit{baseDot}intrabaseDot从而总速率降低。所有时间值都需要四舍五入到最接近的整数。本题的核心任务是根据报文字符串依次输出每个字符的开启/关闭时间序列并正确处理字符间间隔和单词间间隔。解题思路步骤一解析映射表逐行读入每行第一个字符为字母或数字其余部分为摩尔斯码由.和-组成。使用unordered_mapchar, string存储映射关系直到读入单独一行的。步骤二读取每个数据集每个数据集的第一行在之后是速度www接下来读取多行报文直到遇到下一个或EOF\texttt{EOF}EOF。由于换行符除最后一行外视为单词间隔拼接报文时在非最后一行末尾添加一个空格。步骤三提取有效字符及其后间隔类型遍历拼接后的报文字符串仅保留字母和数字将其转换为大写同时记录该字符后面是否紧邻空格或字符串末尾。若后面有空格则该字符后应使用单词间间隔否则使用字符间间隔。步骤四计算时间参数根据www的值计算点时长dot划时长dash 3 * dot字符内间隔intra字符间间隔interChar 3 * intra单词间间隔interWord 9 * intra计算时使用double保持精度最后调用round()四舍五入为整数。步骤五输出每个字符对于每个有效字符输出该字符。根据其摩尔斯码对每个符号输出该符号的开启时间点或划及S。输出字符内间隔及N。输出字符间间隔及N换行。若该字符后是单词间隔则在下一行缩进两个空格输出单词间间隔及N。正确性保证时间计算公式源自题目对131313wpm\texttt{wpm}wpm基准的定义并严格按照低速与高速的区分调整间隔。四舍五入符合输出要求。单词间隔的处理额外行缩进与样例一致。复杂度分析设报文中有效字符总数为MMM每个字符的摩尔斯码平均长度为ccc本题中c≤4c \le 4c≤4或555左右。算法仅需一次遍历报文并查表时间复杂度为O(M⋅c)O(M \cdot c)O(M⋅c)空间复杂度为O(1)O(1)O(1)不考虑存储映射表。整体运行效率极高。代码实现// Morse Code Generation// UVa ID: 730// Verdict: Accepted// Submission Date: 2026-07-08// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);unordered_mapchar,stringmorse;string line;// 读取映射表直到单独一行的 while(getline(cin,line)line!){if(line.empty())continue;stringstreamss(line);charch;string code;sschcode;morse[ch]code;}boolfirstDatasettrue;intwpm;// 循环读取每个数据集while(cinwpm){cin.ignore();// 忽略 wpm 后的换行// 读取报文行直到遇到下一个 或 EOFvectorstringmsgLines;while(getline(cin,line)line!){msgLines.push_back(line);}// 拼接报文换行处插入空格除最后一行string msg;for(size_t i0;imsgLines.size();i){msgmsgLines[i];if(i1msgLines.size())msg ;}// 提取有效字符并记录其后是否有空格单词分隔vectorpairchar,boolchars;// {字符, 是否单词分隔}for(size_t i0;imsg.size();){if(isalnum(msg[i])){charchtoupper(msg[i]);size_t ji1;boolhasSpacefalse;while(jmsg.size()msg[j] ){hasSpacetrue;j;}chars.push_back({ch,hasSpace});ij;}elsei;}// 计算时间参数使用 double 保持精度最后四舍五入constdoublebaseDot60000.0/520.0;// 13 wpm 基准点长doubledot_real,intra_real;if(wpm13){dot_realbaseDot;intra_real60000.0/(wpm*40.0);}else{dot_real60000.0/(wpm*40.0);intra_realdot_real;}intdot(int)round(dot_real);intdash(int)round(3.0*dot_real);intintra(int)round(intra_real);intinterChar(int)round(3.0*intra_real);intinterWord(int)round(9.0*intra_real);// 3 * interChar// 两个数据集之间输出空行if(!firstDataset)cout\n;firstDatasetfalse;// 逐个输出字符for(constautop:chars){charchp.first;boolwordSepp.second;string codemorse[ch];// 查表得到摩尔斯码coutch;// 输出每个符号的 on 和 offoff 为内部间隔for(charc:code){inton(c.)?dot:dash;cout on S;cout intra N;}// 输出字符间间隔cout interChar N;cout\n;// 若该字符后是单词分隔额外输出一行两个空格缩进if(wordSep)cout interWord N\n;}}return0;}总结本题重点在于准确理解摩尔斯码的时序规则与速度之间的关系尤其是低速时通过拉长间隔来降低速率。关键的计算公式和四舍五入步骤需严格遵循。输出格式中单词间间隔的特殊缩进是容易忽略的细节。代码实现简洁只需一次查表和简单循环即可完成体现了模拟题的典型特征。掌握此类模拟题的核心在于仔细阅读题意按部就班实现各个规则并注意输出格式的精确性。