题目描述罗马数字系统基于七个基本大写字母I1\mathrm{I}1I1、V5\mathrm{V}5V5、X10\mathrm{X}10X10、L50\mathrm{L}50L50、C100\mathrm{C}100C100、D500\mathrm{D}500D500、M1000\mathrm{M}1000M1000。与阿拉伯数字类似一个数用罗马数字表示时会将其十进制各位从左到右从最高位到最低位分别转换为罗马表示。例如111111111111写作MCI\mathrm{MCI}MCI105510551055写作MLV\mathrm{MLV}MLV。数字000不出现。对于不能用单个基本字母表示的数码采用重复和累加的原则。例如III3\mathrm{III}3III3XXXII32\mathrm{XXXII}32XXXII32MMVIII2008\mathrm{MMVIII}2008MMVIII2008。只有字母I,X,C,M\mathrm{I,X,C,M}I,X,C,M允许重复且重复次数超过四次是不合理的因为存在更短形式。最终规则规定任何符号不能连续出现超过三次。当处理数字444或999时必须使用减法规则例如444444应写成XLIV\mathrm{XLIV}XLIV而非XXXXIII\mathrm{XXXXIII}XXXXIII。注意I\mathrm{I}I最多只能在V\mathrm{V}V或X\mathrm{X}X前出现一次X\mathrm{X}X最多只能在L\mathrm{L}L或C\mathrm{C}C前出现一次C\mathrm{C}C最多只能在D\mathrm{D}D或M\mathrm{M}M前出现一次。标准罗马数字能表示的最大数是MMCMXCIX3999\mathrm{MMCMXCIX}3999MMCMXCIX3999。提比略皇帝在设计路标时忘记了上述最终规则他只使用累加方式书写罗马数字例如将444444写成XXXXIII\mathrm{XXXXIII}XXXXIII。现在需要修正这些路标每次操作可以擦除一个原有字母或在一个擦除的位置刻入一个新字母。注意不能凭空插入新字母即最终字符串的每个位置要么保留原字符要么被替换为新字符但位置总数可以增加或减少吗实际上修正过程允许擦除和刻入但不能改变字符之间的相对顺序也不能在中间凭空增加空格。也就是说我们只能把原字符串sss和目标标准字符串ttt进行整体平移后重叠重叠区域中相同的字符可以保留其余原字符擦除目标串未匹配的字符刻入。给定一个提比略风格仅加法的罗马数字sss请计算最少需要擦除的字母数eee和刻入的字母数ccc使得sss转换为标准罗马数字ttt。若有多种方案优先使ececec最小再使eee最小。输入格式输入包含多组测试数据每组一行一个字符串sss由罗马数字字符组成表示提比略刻在路标上的错误数字。输入以单独的一行*结束。输出格式对于每组数据输出一行两个整数eee和ccc用空格分隔。样例输入MMMDCCCCLXXXXVIIII XVIIII *输出13 4 5 2注第一个样例对应399939993999标准写法为MMMCMXCIX\mathrm{MMMCMXCIX}MMMCMXCIX最优解为e13,c4e13, c4e13,c4第二个样例191919标准写法为XIX\mathrm{XIX}XIX最优解为e5,c2e5, c2e5,c2。题目分析错误数字的数值计算提比略的写法只使用累加因此给定字符串sss其数值NNN就是每个字符对应数值的简单求和。例如XXXXIII表示101010101114310101010111431010101011143。这个数值NNN是唯一的。标准罗马数字的生成将NNN按照标准罗马数字规则包含减法规则、重复次数限制转换得到目标字符串ttt。标准转换是唯一确定的因为标准罗马数字表示法具有唯一性对于1∼39991\sim 39991∼3999。修正操作的本质我们只能从原字符串sss中擦除一些字符并在擦除的位置刻入新的字符。不允许在原有字符之间插入额外的位置也就是说最终字符串的每个位置要么来自原串的某个位置保留原字符要么来自刻入的新字符。但我们可以通过整体平移的方式让sss和ttt在不同偏移下对齐。例如sss和ttt可以看作两条带子我们可以左右滑动它们使某些位置重叠。重叠位置上如果字符相同则该位置可以直接保留无需操作如果不同则必须擦除原字符并刻入新字符算作一次擦除和一次刻入。对于未重叠的部分sss多出的字符全部擦除ttt多出的字符全部刻入。因此我们只需要选择一种对齐方式即一个偏移量使得重叠位置上相同字符的数量matchmatchmatch尽可能大。因为擦除数e∣s∣−matche |s| - matche∣s∣−match原串中未保留的字符全部擦除刻入数c∣t∣−matchc |t| - matchc∣t∣−match目标串中未匹配的字符全部刻入总操作数ec∣s∣∣t∣−2⋅matchec |s||t| - 2 \cdot matchec∣s∣∣t∣−2⋅match显然matchmatchmatch越大ececec越小且eee也越小因为∣s∣|s|∣s∣固定。因此我们只需要求出所有可能偏移下重叠位置相同字符的最大值。解题思路设n∣s∣n|s|n∣s∣m∣t∣m|t|m∣t∣。我们需要枚举所有可能的偏移量dddsss相对于ttt的位移可为负。暴力枚举偏移并逐字符比较时间复杂度为O((nm)⋅min(n,m))O((nm) \cdot \min(n,m))O((nm)⋅min(n,m))但由于mmm很小标准罗马数字最长不超过151515个字符这个复杂度完全可行。然而直接处理负数偏移容易引起索引越界和繁琐的边界判断。一种更简洁的方法是在sss的左右两侧各补mmm个空格构造一个新字符串s′ss′其长度为n2mn2mn2m。然后在s′ss′上滑动一个长度为mmm的窗口与ttt进行比较。当窗口完全位于补的空格区域时相当于sss整体在ttt的左侧或右侧重叠部分为空匹配数为000。当窗口从左侧空格逐渐滑入sss时等效于sss向右移动当窗口滑出sss进入右侧空格时等效于sss向左移动。这样所有可能的偏移都对应窗口的某个起始位置ddd0≤d≤nm0 \le d \le nm0≤d≤nm。我们只需统计窗口内与ttt相同字符的个数取最大值即可。算法步骤读入一行字符串sss若为*则结束。计算数值NNN遍历sss将每个罗马字符映射为数值并累加。生成标准罗马数字ttt将NNN按千、百、十、个位分别转换为对应的罗马数字段拼接得到ttt。计算最大匹配数matchmatchmatch令mt.length()m t.\text{length}()mt.length()构造s′空格⋯空格⏟m个s空格⋯空格⏟m个s \underbrace{\text{空格}\cdots\text{空格}}_{m\text{个}} s \underbrace{\text{空格}\cdots\text{空格}}_{m\text{个}}s′m个空格⋯空格sm个空格⋯空格。枚举窗口起始位置ddd从000到∣s′∣−m|s|-m∣s′∣−m统计窗口内与ttt相同字符的个数记录最大值。输出e∣s∣−matche |s| - matche∣s∣−matchc∣t∣−matchc |t| - matchc∣t∣−match。正确性说明所有可能的偏移量都对应s′ss′中某个长度为mmm的窗口因为窗口可以完全在左侧空格、部分覆盖sss、完全在右侧空格。因此枚举所有窗口等价于枚举所有偏移。空格不会与任何罗马字母匹配因此非重叠部分贡献为000不影响最大值。最优对齐下保留的字符数matchmatchmatch被正确求出进而得到最优的eee和ccc。复杂度分析每次转换ttt的长度m≤15m \le 15m≤15因此s′ss′的长度n2mn2mn2m与nnn同阶。窗口数量为nm1nm1nm1每个窗口比较mmm个字符总时间复杂度O((nm)⋅m)≤O(15⋅(n15))O((nm) \cdot m) \le O(15 \cdot (n15))O((nm)⋅m)≤O(15⋅(n15))非常高效。空间复杂度O(nm)O(nm)O(nm)。代码实现// The Imperial Problem// UVa ID: 12522// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 获取罗马字符数值inttoValue(charch){switch(ch){caseI:return1;caseV:return5;caseX:return10;caseL:return50;caseC:return100;caseD:return500;caseM:return1000;default:return0;}}// 整数转标准罗马数字stringtoRoman(intnum){string thousands[]{,M,MM,MMM};string hundreds[]{,C,CC,CCC,CD,D,DC,DCC,DCCC,CM};string tens[]{,X,XX,XXX,XL,L,LX,LXX,LXXX,XC};string ones[]{,I,II,III,IV,V,VI,VII,VIII,IX};returnthousands[num/1000]hundreds[(num%1000)/100]tens[(num%100)/10]ones[num%10];}// 计算最大匹配数补空格滑动窗口intmaxMatch(conststrings,conststringt){intns.size(),mt.size();// 原串左右补 m 个空格使所有偏移对齐都覆盖string paddedstring(m, )sstring(m, );inttotalLenpadded.size();intbest0;// 滑动窗口长度为 m比较与 t 的相同字符数for(intd0;dtotalLen-m;d){intmatch0;for(inti0;im;i)if(padded[di]t[i])match;if(matchbest)bestmatch;}returnbest;}intmain(){ios::sync_with_stdio(false);cin.tie(0);string s;while(cins){if(s*)break;intvalue0;for(charch:s)valuetoValue(ch);string targettoRoman(value);intmatchmaxMatch(s,target);intes.size()-match;intctarget.size()-match;coute c\n;}return0;}总结本题的关键在于正确理解“只能擦除和刻入不能插入”的约束意识到这等价于两个字符串在整体平移对齐下求最大相同字符数。通过在原串两侧补空格将偏移枚举转化为滑动窗口匹配极大地简化了边界处理使代码简洁且不易出错。此外标准罗马数字的生成需熟练掌握罗马数字的转换规则。本题的时间复杂度极低适合用暴力枚举所有偏移的方式解决体现了对问题本质的深入理解。
