企业官网建设流程全解析

题目描述

题目要求根据七段数码管的ASCII\texttt{ASCII}ASCII表示还原银行账号。每个账号由999位数字组成，且满足校验和公式：
(d1+2×d2+3×d3+⋯+9×d9) mod 11=0 (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​)mod11=0
其中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数组）：

损坏处理

由于损坏只能导致线段缺失（即111变为000），不能产生多余线段。因此，对于一个损坏的数字，其编码必须是某个标准数字编码的子集（按位与等于原编码）。参考代码中预先生成了每个数字所有可能的损坏编码（通过递归清除位得到），存入garbledNumbers。

校验和

校验和公式从右向左计算。设d1d_1d1​是最右边（个位）的数字，d9d_9d9​是最左边的数字。计算∑i=19i×di mod 11=0\sum_{i=1}^{9} i \times d_i \bmod 11 = 0∑i=19​i×di​mod11=0。

算法步骤

对于每个测试用例：

1. 读取333行，每行272727个字符。将空格视为000，非空格视为111，得到每个数字的999位二进制编码。
2. 尝试将每个数字的编码与标准编码匹配：
   • 若匹配成功，记录该数字。
   • 若匹配失败，记录该位置为损坏（garbledIndex），并记录损坏后的编码值。
3. 若存在损坏位置：
   • 遍历000到999的所有数字，检查该数字的损坏编码集合是否包含当前损坏编码。若是，则将该位置替换为该数字，并检查校验和。
   • 统计满足校验和的数字个数。若唯一解则输出，若多解则输出ambiguous，若无解则输出failure。
4. 若无损坏位置：
   • 直接检查校验和。若成立，则输出该数字串。
   • 若不成立，则需要考虑可能有一位数字被损坏（但扫描时未缺失任何线段？题目保证最多一位损坏，但此情况意味着虽然编码完整，但实际数字可能被误识别）。此时需要尝试将每一位数字替换为其他可能的数字（根据预先生成的候选列表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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<string>digits={"010101111","000001001","010011110","010011011","000111001","010110011","010110111","010001001","010111111","010111011"};vector<set<int>>garbledNumbers(10);voidbacktrack(intindexer,intnumber){for(inti=1,mask=1;i<=9;i++,mask<<=1)if((number&mask)>0){intnext_number=number^mask;garbledNumbers[indexer].insert(next_number);backtrack(indexer,next_number);}}boolchecksum(vector<int>&accountDigits){intsum=0;for(inti=9;i>=1;i--)sum+=i*accountDigits[9-i];return(sum%11)==0;}voiddisplay(vector<int>answer,intcountOfSolutions){if(countOfSolutions>=2)cout<<"ambiguous\n";elseif(countOfSolutions==0)cout<<"failure\n";else{for(autodigit:answer)cout<<digit;cout<<'\n';}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);map<int,int>numbers;for(inti=0;i<=9;i++){bitset<9>converter(digits[i]);intvalue=(int)converter.to_ulong();numbers[value]=i;backtrack(i,value);}string line;getline(cin,line);intcases=stoi(line);for(inti=1;i<=cases;i++){// read the segment presentation of digitvector<string>account(3);for(intj=0;j<3;j++){getline(cin,line);string segments;for(intk=0;k<line.length()&&k<27;k++)segments+=(line[k]==' '?'0':'1');while(segments.length()<27)segments+='0';account[j]=segments;}// find if garbled number exist or notvector<int>accountDigits;intgarbledIndex=-1,garbledValue;for(intj=0;j<9;j++){string digitText;for(intk=0;k<3;k++)digitText+=account[k].substr(j*3,3);bitset<9>binary(digitText);intvalue=(int)binary.to_ulong();if(numbers.find(value)!=numbers.end())accountDigits.push_back(numbers[value]);else{accountDigits.push_back(-1);garbledIndex=j;garbledValue=value;}}// one digit is garbledintcountOfSolutions=0;vector<int>answer(accountDigits);if(garbledIndex!=-1){for(intj=0;j<=9;j++)if(garbledNumbers[j].find(garbledValue)!=garbledNumbers[j].end()){accountDigits[garbledIndex]=j;if(checksum(accountDigits)){answer.assign(accountDigits.begin(),accountDigits.end());countOfSolutions++;}if(countOfSolutions>=2)break;}display(answer,countOfSolutions);continue;}// check the account is valid or notif(checksum(accountDigits)){display(answer,1);continue;}// find others solutionsvector<string>candidates={"8","034789","8","89","89","689","8","0389","8","8"};vector<int>backup(accountDigits);countOfSolutions=0;for(intj=0;j<9;j++){for(autoascii:candidates[backup[j]]){accountDigits[j]=ascii-'0';if(checksum(accountDigits)){answer.assign(accountDigits.begin(),accountDigits.end());countOfSolutions++;}if(countOfSolutions>=2)gotoskip;}accountDigits.assign(backup.begin(),backup.end());}skip:display(answer,countOfSolutions);}return0;}