题目描述Code-11\texttt{Code-11}Code-11是一种用于电信设备标签的条形码系统可编码数字000到999、连字符-以及起始/终止字符。每个字符由555个交替的暗色和亮色条组成以暗色条开始每个条的宽度为窄或宽。字符之间由窄亮色条分隔。条形码以起始字符开始以终止字符结束消息后附加两个校验字符CCC和KKK。给定条形码阅读器检测到的各区域宽度要求解码出原始消息或判断条形码是否无效。输入格式输入包含多个测试用例。每个测试用例第一行是一个整数mmmm≤150m \le 150m≤150表示检测到的区域数量。接下来mmm个整数d1…dmd_1 \ldots d_md1…dm1≤di≤2001 \le d_i \le 2001≤di≤200表示每个区域的传感器数量。数据以暗色条开始和结束。最后一个测试用例后跟一个整数000。输出格式对于每个测试用例输出一行Case X:后跟解码结果。若成功解码输出消息字符序列不含校验字符。若CCC校验字符错误输出bad C若KKK校验字符错误输出bad K若条形码因宽度超出允许范围、起始/终止码缺失或其他无效条件而无法解码输出bad code。样例输入59 10 20 20 10 10 10 20 10 10 20 10 10 10 10 20 10 20 10 10 10 20 10 20 10 20 10 20 10 10 10 10 10 20 10 10 10 10 10 10 20 20 10 20 10 10 20 10 10 20 10 10 10 20 10 10 20 20 10 10 35 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 35 10 10 20 20 10 10 20 10 10 10 20 10 10 20 10 10 20 10 10 10 20 10 20 10 20 10 10 10 10 10 10 10 10 20 20 10样例输出Case 1: 123-45 Case 2: bad code Case 3: bad K题目分析本题要求解码Code-11\texttt{Code-11}Code-11条形码。每个字符由555个条组成字符之间由111个窄亮色条分隔。完整的条形码结构为起始字符555条分隔条111条消息字符每个555条之间111条分隔分隔条CCC校验字符555条分隔条KKK校验字符555条分隔条终止字符555条。总区域数mmm满足m51(n2)×6−15m 5 1 (n2) \times 6 - 1 5m51(n2)×6−15需要仔细计算。起始字符555条然后分隔条111条然后每个消息字符555条加分隔条111条共nnn个消息字符然后CCC校验字符555条加分隔条111条然后KKK校验字符555条加分隔条111条最后终止字符555条。总数为51n×66656n295 1 n \times 6 6 6 5 6n 2951n×66656n29。因此mmm必须满足m≥29m \ge 29m≥29且(m−29) mod 60(m-29) \bmod 6 0(m−29)mod60。解码步骤将检测到的区域宽度分类为窄或宽。由于宽条宽度约为窄条的两倍且存在±5%\pm 5\%±5%的误差需要确定阈值。首先找到所有区域的最小值narrownarrownarrow和最大值widewidewide取中间值middle(narrowwide)/2middle (narrow wide) / 2middle(narrowwide)/2。对于每个区域若其值小于middlemiddlemiddle则认为是窄条否则认为是宽条。但为了处理误差还需验证宽窄比例是否在允许范围内将所有窄条值乘以222然后重新计算最小值和最大值检查wide×95≤narrow×105wide \times 95 \le narrow \times 105wide×95≤narrow×105是否成立。若不成立则输出bad code。将每个区域映射为000窄或111宽得到二进制串。检查起始和终止字符是否为00110。若正向不匹配尝试反向因为条形码可能从右向左扫描。若仍不匹配输出bad code。检查每个字符之间的分隔条是否均为窄条即对应位置为0。若不满足输出bad code。提取每个字符的555位编码查表得到对应的数字或连字符。若编码不在表中输出bad code。计算CCC校验字符设消息字符为c1,…,cnc_1, \ldots, c_nc1,…,cn权重w(ci)w(c_i)w(ci)为数字000到999对应000到999连字符为101010。CCC的权重为(∑i1n((n−i) mod 101)×w(ci)) mod 11\left(\sum_{i1}^{n} ((n-i) \bmod 10 1) \times w(c_i)\right) \bmod 11(∑i1n((n−i)mod101)×w(ci))mod11。若计算值与解码得到的CCC不符输出bad C。计算KKK校验字符将CCC视为第n1n1n1个字符权重公式为(∑i1n1((n−i1) mod 91)×w(ci)) mod 11\left(\sum_{i1}^{n1} ((n-i1) \bmod 9 1) \times w(c_i)\right) \bmod 11(∑i1n1((n−i1)mod91)×w(ci))mod11。若计算值与解码得到的KKK不符输出bad K。若全部通过输出消息字符序列。解题思路首先根据区域数量判断基本格式是否正确。然后通过阈值将宽度二值化。为了处理打印误差先计算所有区域的最小值和最大值取中间值作为初始阈值。将小于阈值的区域视为窄条大于等于阈值的视为宽条。但为了更精确可以将所有窄条的值乘以222来模拟宽条然后重新计算最小值和最大值检查宽条与窄条的比例是否在95%95\%95%到105%105\%105%之间。若不满足则条形码无效。接着将二值化后的序列拼接成字符串。检查起始和终止的555位是否为00110。由于扫描方向可能相反若正向不匹配则反转字符串再检查。然后检查所有分隔条位置是否为0。接着按每666位一组555位字符111位分隔提取字符编码查表转换为数字。若遇到未知编码输出bad code。解码完成后根据公式计算CCC和KKK校验值与解码得到的校验字符比较。注意CCC校验使用消息字符KKK校验使用消息字符加上CCC字符。若CCC错误输出bad C若KKK错误输出bad K。全部正确则输出消息字符不含校验字符。时间复杂度为O(m)O(m)O(m)空间复杂度为O(m)O(m)O(m)对于m≤150m \le 150m≤150非常高效。代码实现#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intbar[160],m,cases0;string flag00110;string characters0123456789-;mapstring,intencoding{{00001,0},{10001,1},{01001,2},{11000,3},{00101,4},{10100,5},{01100,6},{00011,7},{10010,8},{10000,9},{00100,10}};while(cinm,m0){coutCase cases: ;for(inti0;im;i)cinbar[i];if(m29||(m-29)%6!0){coutbad code\n;continue;}intwide,narrow;wide0,narrow0x3f3f3f3f;for(inti0;im;i)widemax(wide,bar[i]),narrowmin(narrow,bar[i]);doublemiddle(narrowwide)/2.0;wide0,narrow0x3f3f3f3f;for(inti0;im;i){intv0;if(bar[i]middle)vbar[i]*2;elsevbar[i];widemax(wide,v),narrowmin(narrow,v);}if(wide*95narrow*105){coutbad code\n;continue;}string code;narrowbar[0],wide2*narrow;for(inti0;im;i){if(bar[i]middle)code0;elsecode1;}boolgoodcode.substr(0,5)flagcode.substr(code.length()-5)flag;if(!good){reverse(code.begin(),code.end());goodcode.substr(0,5)flagcode.substr(code.length()-5)flag;}if(!good){coutbad code\n;continue;}for(inti5;icode.length();i6)if(code[i]!0){goodfalse;break;}if(!good){coutbad code\n;continue;}vectorintdigits;for(inti6;icode.length()-5;i6){string blockcode.substr(i,5);if(encoding.find(block)encoding.end()){goodfalse;break;}digits.push_back(encoding[block]);}if(!good){coutbad code\n;continue;}intndigits.size()-2,mod0;for(inti1;in;i)mod((n-i)%101)*digits[i-1];mod%11;if(mod!digits[n]){coutbad C\n;continue;}ndigits.size()-1,mod0;for(inti1;in;i)mod((n-i)%91)*digits[i-1];mod%11;if(mod!digits[n]){coutbad K\n;continue;}for(inti0;idigits.size()-2;i)coutcharacters[digits[i]];cout\n;}return0;}总结本题的核心在于Code-11\texttt{Code-11}Code-11条形码的解码过程包括宽度二值化、起始/终止码识别、分隔条验证、字符查表以及双重校验。关键点在于处理打印误差时通过将窄条宽度乘以222来模拟宽条并验证宽窄比例是否在允许范围内。同时需要支持反向扫描即当正向解码失败时尝试反转序列。校验公式中注意取模运算的优先级和范围。整体算法思路清晰实现细节较多适用于题目给定的约束条件。