题目描述题目要求根据七段数码管的ASCII\texttt{ASCII}ASCII表示还原银行账号。每个账号由999位数字组成且满足校验和公式(d12×d23×d3⋯9×d9) mod 110 (d_1 2 \times d_2 3 \times d_3 \dots 9 \times d_9) \bmod 11 0(d1​2×d2​3×d3​⋯9×d9​)mod110其中d9d_9d9​是最左边的数字d1d_1d1​是最右边的数字即数字从右向左编号。输入为扫描后的图像可能包含缺失的线段即某些本该亮的线段缺失但不会包含多余的线段。假设若输入直接表示一个有效账号则其为原始账号否则最多有一位数字存在缺失线段即只有一个数字被损坏。需要输出还原后的999位数字若无解输出failure若多解输出ambiguous。输入格式第一行一个整数NNN表示测试用例的数量。每个测试用例由333行组成每行272727个字符表示999个数字的七段显示每个数字占3×33 \times 33×3的网格。字符为|、_或空格。输出格式对于每个测试用例输出一行若唯一确定则输出999位数字若无解则输出failure若多解则输出ambiguous。样例输入4 _ _ _ _ _ _ _ _ |_||_||_||_||_||_||_||_||_| | | | | | | | | | _ _ _ _ _ _ _ _ |_||_||_||_||_||_||_||_||_| | | | | | | | | | _ _ _ _ _ _ _ _ |_||_||_||_||_||_||_||_||_| | | | | | | | | | _ _ _ _ _ _ _ _ |_||_||_||_||_||_||_||_||_| | | | | | | | | |输出123456789 ambiguous failure 878888888题目分析本题的核心是将七段数码管的ASCII\texttt{ASCII}ASCII表示转换为二进制编码然后根据编码匹配数字并处理可能的损坏情况。七段编码每个数字在3×33 \times 33×3网格中显示共999个位置333行×3\times 3×3列。将每个位置是否有笔画映射为二进制位111表示有笔画000表示无。标准数字的编码如下按行主序排列参考代码中的digits数组数字编码000010101111010101111010101111111000001001000001001000001001222010011110010011110010011110333010011011010011011010011011444000111001000111001000111001555010110011010110011010110011666010110111010110111010110111777010001001010001001010001001888010111111010111111010111111999010111011010111011010111011损坏处理由于损坏只能导致线段缺失即111变为000不能产生多余线段。因此对于一个损坏的数字其编码必须是某个标准数字编码的子集按位与等于原编码。参考代码中预先生成了每个数字所有可能的损坏编码通过递归清除位得到存入garbledNumbers。校验和校验和公式从右向左计算。设d1d_1d1​是最右边个位的数字d9d_9d9​是最左边的数字。计算∑i19i×di mod 110\sum_{i1}^{9} i \times d_i \bmod 11 0∑i19​i×di​mod110。算法步骤对于每个测试用例读取333行每行272727个字符。将空格视为000非空格视为111得到每个数字的999位二进制编码。尝试将每个数字的编码与标准编码匹配若匹配成功记录该数字。若匹配失败记录该位置为损坏garbledIndex并记录损坏后的编码值。若存在损坏位置遍历000到999的所有数字检查该数字的损坏编码集合是否包含当前损坏编码。若是则将该位置替换为该数字并检查校验和。统计满足校验和的数字个数。若唯一解则输出若多解则输出ambiguous若无解则输出failure。若无损坏位置直接检查校验和。若成立则输出该数字串。若不成立则需要考虑可能有一位数字被损坏但扫描时未缺失任何线段题目保证最多一位损坏但此情况意味着虽然编码完整但实际数字可能被误识别。此时需要尝试将每一位数字替换为其他可能的数字根据预先生成的候选列表candidates检查校验和统计解的数量。候选列表说明参考代码中的candidates数组定义了每个数字可能被误识别为的其他数字。例如034789表示数字000可能被误认为000、333、444、777、888、999等。这实际上是所有与当前数字的编码相差不超过一个损坏即111变000的数字集合。复杂度分析每个测试用例只需检查最多9×109 \times 109×10种可能性完全可接受。代码实现// Bank (Not Quite O.C.R.)// UVa ID: 433// Verdict: Accepted// Submission Date: 2016-07-19// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorstringdigits{010101111,000001001,010011110,010011011,000111001,010110011,010110111,010001001,010111111,010111011};vectorsetintgarbledNumbers(10);voidbacktrack(intindexer,intnumber){for(inti1,mask1;i9;i,mask1)if((numbermask)0){intnext_numbernumber^mask;garbledNumbers[indexer].insert(next_number);backtrack(indexer,next_number);}}boolchecksum(vectorintaccountDigits){intsum0;for(inti9;i1;i--)sumi*accountDigits[9-i];return(sum%11)0;}voiddisplay(vectorintanswer,intcountOfSolutions){if(countOfSolutions2)coutambiguous\n;elseif(countOfSolutions0)coutfailure\n;else{for(autodigit:answer)coutdigit;cout\n;}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);mapint,intnumbers;for(inti0;i9;i){bitset9converter(digits[i]);intvalue(int)converter.to_ulong();numbers[value]i;backtrack(i,value);}string line;getline(cin,line);intcasesstoi(line);for(inti1;icases;i){// read the segment presentation of digitvectorstringaccount(3);for(intj0;j3;j){getline(cin,line);string segments;for(intk0;kline.length()k27;k)segments(line[k] ?0:1);while(segments.length()27)segments0;account[j]segments;}// find if garbled number exist or notvectorintaccountDigits;intgarbledIndex-1,garbledValue;for(intj0;j9;j){string digitText;for(intk0;k3;k)digitTextaccount[k].substr(j*3,3);bitset9binary(digitText);intvalue(int)binary.to_ulong();if(numbers.find(value)!numbers.end())accountDigits.push_back(numbers[value]);else{accountDigits.push_back(-1);garbledIndexj;garbledValuevalue;}}// one digit is garbledintcountOfSolutions0;vectorintanswer(accountDigits);if(garbledIndex!-1){for(intj0;j9;j)if(garbledNumbers[j].find(garbledValue)!garbledNumbers[j].end()){accountDigits[garbledIndex]j;if(checksum(accountDigits)){answer.assign(accountDigits.begin(),accountDigits.end());countOfSolutions;}if(countOfSolutions2)break;}display(answer,countOfSolutions);continue;}// check the account is valid or notif(checksum(accountDigits)){display(answer,1);continue;}// find others solutionsvectorstringcandidates{8,034789,8,89,89,689,8,0389,8,8};vectorintbackup(accountDigits);countOfSolutions0;for(intj0;j9;j){for(autoascii:candidates[backup[j]]){accountDigits[j]ascii-0;if(checksum(accountDigits)){answer.assign(accountDigits.begin(),accountDigits.end());countOfSolutions;}if(countOfSolutions2)gotoskip;}accountDigits.assign(backup.begin(),backup.end());}skip:display(answer,countOfSolutions);}return0;}