题目分析本题要求判断给定的罗马数字算式在两种规则下的正确性罗马数字算术规则判断算式是否满足罗马数字的减法表示法规则并且数值计算正确。阿拉伯数字编码规则将每个罗马字母映射为000-999的一个数字不同字母映射到不同数字判断是否存在映射使得算式成立数字不能有前导零不能单独为零。输入格式为A B C其中AAA、BBB、CCC是合法的罗马数字长度不超过999。需要输出两个单词第一个表示罗马算术是否正确Correct/Incorrect第二个表示阿拉伯编码是否存在解impossible/valid/ambiguous。解题思路第一部分罗马算术判断判断罗马数字算术是否正确分两步检查AAA、BBB、CCC是否符合合法的罗马数字表示法本题采用标准减法表示法如444写作IV而非IIII。将三个罗马数字转换为数值验证ABCA B CABC是否成立。罗马数字转数值的规则从左到右扫描如果当前字母的值小于右边字母的值则做减法加右边减当前否则直接累加。第二部分阿拉伯数字编码判断这是一个带约束的字母到数字的映射问题使用回溯法DFS\texttt{DFS}DFS枚举所有可能的映射收集算式中出现的所有不同罗马字母最多777个IVXLCDM。为这些字母分配000-999中不同的数字。约束条件每个罗马数字的首字母不能映射到000无前导零。映射后的数值不能为000零不会单独出现。枚举所有合法映射统计使ABCA B CABC成立的映射个数个数为000→impossible个数为111→valid个数≥2\ge 2≥2→ambiguous由于最大字母数为777全排列数为P(10,7)604800P(10, 7) 604800P(10,7)604800可以接受。但为了效率可以在找到两个解后提前终止。代码实现// Roman Numerals// UVa ID: 185// Verdict: Accepted// Submission Date: 2016-03-13// UVa Run Time: 0.100s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 存储算式分解后的三个部分string leftPart,rightPart,lastPart;// 罗马数字的列分类左列I,X,C,M可重复最多3次右列V,L,D最多1次string leftColumnIXCM,rightColumnVLD,allRomanIVXLCDM;// 各罗马字母对应的数值intnumbers[]{1,5,10,50,100,500,1000};// 正则表达式用于验证罗马数字是否符合标准减法表示法string patternR(^M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$);regexromanExp(pattern,regex_constants::ECMAScript);// 判断一个字符串是否为合法的标准罗马数字boolisRoman(stringroman){returnregex_match(roman,romanExp);}// 将合法的罗马数字转换为整数值intromanToNumber(string roman){intnumber0,index0;while(indexroman.length()-1){intfirstallRoman.find(roman[index]);intsecondallRoman.find(roman[index1]);// 如果左边小于右边则做减法if(numbers[first]numbers[second]){numbernumbers[second]-numbers[first];index2;}else{numbernumbers[first];index;}}// 处理最后一个字符if(indexroman.length())numbernumbers[allRoman.find(roman[index])];returnnumber;}// 解析输入行提取 A、B、C 三个部分voidparse(stringline){intplusIndexline.find();intequalIndexline.find();leftPartline.substr(0,plusIndex);rightPartline.substr(plusIndex1,equalIndex-plusIndex-1);lastPartline.substr(equalIndex1);}// 判断罗马算术是否正确stringRoman(){// 任一字符串不是合法罗马数字则算式不正确if(!isRoman(leftPart)||!isRoman(rightPart)||!isRoman(lastPart))returnIncorrect;return(romanToNumber(leftPart)romanToNumber(rightPart)romanToNumber(lastPart))?Correct:Incorrect;}// 用于回溯搜索的全局变量inttimes0;// 找到的解的个数boolfinishedfalse;// 是否提前终止搜索setstringsolutions;// 存储映射关系避免重复计数vectorintdigits;// 当前映射的数字vectorboolused;// 数字是否已被使用string matchNeed;// 算式中出现的不同罗马字母// 将映射后的阿拉伯数字字符串转换为整数intarabicToNumber(string arabic){intnumber0;for(inti0;iarabic.length();i)numbernumber*10digits[matchNeed.find(arabic[i])];returnnumber;}// 深度优先搜索枚举所有可能的映射voidbacktrack(intindex){if(finished)return;// 所有字母都已分配数字if(indexmatchNeed.length()){intleftNumber,rightNumber,lastNumber;// 检查前导零每个罗马数字的首字母不能映射到0leftNumberdigits[matchNeed.find(leftPart[0])];rightNumberdigits[matchNeed.find(rightPart[0])];lastNumberdigits[matchNeed.find(lastPart[0])];if(leftNumber0||rightNumber0||lastNumber0)return;// 转换为整数leftNumberarabicToNumber(leftPart);rightNumberarabicToNumber(rightPart);lastNumberarabicToNumber(lastPart);// 零不能单独出现数值不能为0if(leftNumber0||rightNumber0||lastNumber0)return;// 检查算式是否成立if(leftNumberrightNumberlastNumber){// 记录映射关系用于去重string pair;for(inti0;imatchNeed.length();i){pairmatchNeed[i];pair(char)(digits[i]0);}if(solutions.count(pair)0){solutions.insert(pair);times;}}// 找到至少两个解时提前终止if(times2)finishedtrue;return;}// 为当前位置的字母分配一个未使用的数字for(inti0;iused.size();i)if(used[i]false){used[i]true;digits[index]i;backtrack(index1);used[i]false;}}// 判断阿拉伯数字编码的可能性stringArabic(stringline){// 初始化收集算式中出现的所有不同罗马字母digits.clear();matchNeed.clear();for(inti0;iallRoman.length();i)if(line.find(allRoman[i])!line.npos){matchNeedallRoman[i];digits.push_back(0);}// 初始化数字使用标记used.clear();for(inti0;i9;i)used.push_back(false);// 重置搜索状态solutions.clear();finishedfalse;times0;// 开始回溯枚举backtrack(0);// 根据解的个数返回结果if(times0)returnimpossible;elseif(times1)returnvalid;elsereturnambiguous;}intmain(){cin.tie(0);cout.sync_with_stdio(false);string line;while(getline(cin,line),line!#){// 去除行中的空白字符for(intiline.length()-1;i0;i--)if(isblank(line[i]))line.erase(line.begin()i);parse(line);coutRoman() Arabic(line)\n;}return0;}总结本题综合考查了字符串处理、正则表达式、数值转换以及回溯搜索。关键在于罗马数字的合法表示校验使用正则表达式最为简洁。阿拉伯编码部分需要仔细处理前导零和零值约束。回溯搜索时通过提前终止找到两个解即退出可以显著提高效率。