题目描述数字可以用阿拉伯数字或基数词大写数字来表示。在支付支票中用户需要以两种格式书写同一个数字一处使用阿拉伯数字格式如203203203另一处使用基数词格式如duzentos e tres。假设新一代光学字符识别OCR\texttt{OCR}OCR设备的误差可以忽略不计一家每天处理数十万张支付支票的葡萄牙银行希望开发一个应用程序用于验证每张支票上以基数词格式书写的数字是否与阿拉伯数字格式书写的数字一致从而只将不一致的情况交由人工处理。本题要求将给定的基数词格式的数字转换为阿拉伯数字格式。输入格式程序输入为一个文本文件。第一行包含一个阿拉伯数字表示后续行数。接下来的每一行包含一个以基数词格式书写的数字且该数字按照葡萄牙语正字法和语法正确表示。为方便起见题目给出了允许出现的标点符号和构成基数词的单词列表为简化当前编程问题而限制的集合e、zero、um、dois、tres、quatro、cinco、seis、sete、oito、nove、dez、onze、doze、treze、catorze、quatorze、quinze、dezasseis、dezesseis、dezassete、dezessete、dezoito、dezanove、dezenove、vinte、trinta、quarenta、cinquenta、sessenta、setenta、oitenta、noventa、cem、cento、duzentos、trezentos、quatrocentos、quinhentos、seiscentos、setecentos、oitocentos、novecentos、mil、milhao、milhoes、biliao、bilioes、bilhao、bilhoes。输出格式程序输出为一个文本文件行数与输入文件相同。其第一行与输入文件的第一行完全相同。随后的第iii行包含输入文件第iii行中以基数词表示的数字所对应的阿拉伯数字格式。样例输入12 quatro vinte e tres cento e vinte e sete mil doze mil duzentos e cinco quatrocentos mil e cinco quatrocentos e trinta e sete mil e cem um milhao, cem mil quinhentos e seis trezentos e trinta e dois bilioes, quinze mil cento e oito mil milhoes duzentos bilioes, setenta e oito milhoes, sete mil e cem quinhentos bilioes e tres mil样例输出12 4 23 127 1000 12205 400005 437100 1100506 332000015108 1000000000 200078007100 500000003000题目分析本题要求将葡萄牙语基数词转换为阿拉伯数字。基数词的构成规则遵循十进制分级结构每三位为一级级内使用百位、十位和个位组合级间使用mil、milhao、biliao等词连接。转换的关键在于正确识别每个单词所代表的数值并根据其相对大小关系确定乘法与加法的组合方式。葡萄牙语基数词的表达具有层次性。例如quatrocentos e trinta e sete mil e cem表示437×1000100437100437 \times 1000 100 437100437×1000100437100。其中mil作为乘数作用于其前面的数值而e仅作为连接词不参与数值计算。对于更大的数如trezentos e trinta e dois bilioes, quinze mil cento e oito mil milhoes需要按照biliao、milhao等词的层级逐级分解。由于题目保证输入格式正确可以依据单词的数值大小关系进行解析当遇到一个比当前累积值更大的单位词时说明前面的数值需要与该单位相乘。具体实现时可以使用一个队列累积当前级的数值当遇到更大的单位时将队列中所有数值求和后乘以该单位并累加到总结果中。解题思路首先建立单词到数值的映射表包括所有个位、十位、百位、千位、百万位和十亿位的单词及其变体如catorze与quatorze、dezasseis与dezesseis等均映射到相同数值。读取输入行后使用字符串流逐个读取单词忽略e和标点符号。维护一个队列number用于累积当前层级的数值。对于每个有效单词获取其对应数值current。若队列非空且current大于队首元素则说明current是一个更大的单位词如mil、milhao等此时将队列中所有数值求和得到prefix计算prefix * current并累加到总结果total中同时清空队列。否则将current压入队列。处理完所有单词后将队列中剩余的数值求和并累加到total中输出total即为转换结果。该算法的时间复杂度为O(L)O(L)O(L)其中LLL为输入行的单词数空间复杂度为O(L)O(L)O(L)能够高效处理题目规模的数据。代码实现// Number Format Translator// UVa ID: 943// Verdict: Accepted// Submission Date: 2017-03-16// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);mapstring,intdigits{{zero,0},{um,1},{dois,2},{tres,3},{quatro,4},{cinco,5},{seis,6},{sete,7},{oito,8},{nove,9},{dez,10},{onze,11},{doze,12},{treze,13},{catorze,14},{quatorze,14},{quinze,15},{dezasseis,16},{dezesseis,16},{dezassete,17},{dezessete,17},{dezoito,18},{dezanove,19},{dezenove,19},{vinte,20},{trinta,30},{quarenta,40},{cinquenta,50},{sessenta,60},{setenta,70},{oitenta,80},{noventa,90},{cem,100},{cento,100},{duzentos,200},{trezentos,300},{quatrocentos,400},{quinhentos,500},{seiscentos,600},{setecentos,700},{oitocentos,800},{novecentos,900},{mil,1000},{milhao,1000000},{milhoes,1000000},{biliao,1000000000},{bilioes,1000000000},{bilhao,1000000000},{bilhoes,1000000000}};intcases0;cincases;coutcases\n;cin.ignore(1024,\n);for(intc1;ccases;c){string line;getline(cin,line);istringstreamiss(line);longlongtotal0;queuelonglongnumber;string word;while(issword){if(digits.find(word)digits.end())continue;longlongcurrentdigits[word];if(!number.empty()currentnumber.front()){longlongprefix0;while(!number.empty()){prefixnumber.front();number.pop();}totalprefix*current;}elsenumber.push(current);}longlongremainder0;while(!number.empty()){remaindernumber.front();number.pop();}totalremainder;couttotal\n;}return0;}总结本题的关键在于理解葡萄牙语基数词的层级结构并利用数值大小关系判断何时进行乘法运算。通过队列累积当前层级的数值遇到更大的单位词时进行乘法并累加可以正确处理mil、milhao、biliao等词的组合。需要注意单词变体的映射如catorze与quatorze、连接词e和标点符号的忽略以及使用646464位整数存储结果。时间复杂度为O(L)O(L)O(L)空间复杂度为O(L)O(L)O(L)能够高效完成转换任务。