题目描述
题目模拟了一个七段数码管显示器的测试过程。显示器由七个发光二极管（LED\texttt{LED}LED）段组成，分别标记为a,b,c,d,e,f,ga, b, c, d, e, f, ga,b,c,d,e,f,g。每个数字000到999对应一组亮（Y\texttt{Y}Y）或灭（N\texttt{N}N）的段组合。
在测试过程中，某些段可能从一开始就损坏（始终不亮），更多段可能在测试过程中损坏。损坏的段一旦损坏就保持不亮，不会恢复，也不会出现损坏的段变成亮的情况。测试设备观察到一个连续的显示序列（每个显示状态由777个Y/N\texttt{Y}/\texttt{N}Y/N字符描述），需要判断该序列是否可能是一个合法的“倒计数”序列（即从某个数字开始依次递减，如9,8,7,…9,8,7,\ldots9,8,7,…），允许段损坏随时间增加。
输入格式
输入包含多组数据。每组数据格式如下：
- 第一行一个整数NNN（0<N<110 < N < 110<N<11），表示观察到的显示状态数量。
- 接下来NNN行，每行一个长度为777的字符串，由Y\texttt{Y}Y和N\texttt{N}N组成，表示该状态下七个段的亮灭情况（第一个字符对应aaa段）。
- 输入以N=0N = 0N=0表示结束。
输出格式
对于每组数据，输出一行，内容为MATCH\texttt{MATCH}MATCH或MISMATCH\texttt{MISMATCH}MISMATCH，分别表示该序列可能是合法的倒计数序列或不可能。
样例
输入
1 YYYYYNN 2 NNNNNNN NNNNNNN 2 YYYYYYY YYYYYYY 3 YYYYYYY YNYNYYY NYNYNYN 3 YYYYYYY YNYNYNN NYNYNYN 3 YYYYYYY YNYNYNN NYNYNYN 4 YYYYYYY NYNNNNN NNYYYYNN NNNYNNN 3 NNNNNNN YNNNNNN NNNNYNN 0输出
MATCH MATCH MISMATCH MATCH MATCH MISMATCH MATCH MATCH题目分析
本题的核心是判断给定的观察序列是否可能对应于某个倒计数序列，允许段在测试过程中损坏（从亮变为灭），但不允许修复（灭变为亮）。
数字编码
题目给出了数字000到999的七段显示编码：
| 数字 | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| 0 | Y | Y | Y | Y | Y | N | N |
| 1 | N | Y | Y | N | N | N | N |
| 2 | Y | Y | N | Y | Y | N | Y |
| 3 | Y | Y | Y | Y | N | N | Y |
| 4 | N | Y | Y | N | N | Y | Y |
| 5 | Y | N | Y | Y | N | Y | Y |
| 6 | Y | N | Y | Y | Y | Y | Y |
| 7 | Y | Y | Y | N | N | N | N |
| 8 | Y | Y | Y | Y | Y | Y | Y |
| 9 | Y | Y | Y | Y | N | Y | Y |
倒计数序列
倒计数序列是从某个数字开始，每次减111，直到000。例如9,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,0。序列可以只包含其中连续的一段，如5,4,35,4,35,4,3。
设观察到的显示状态数为NNN，则可能的起始数字必须满足：起始数字≥N−1\ge N-1≥N−1（因为需要递减N−1N-1N−1次到达000），且起始数字≤9\le 9≤9。因此起始数字的取值范围为[max(0,N−1),9][\max(0, N-1), 9][max(0,N−1),9]。
损坏规则
设某个段在初始状态（观察序列的第一个显示）时的状态为observed\textit{observed}observed，对应的数字编码状态为expected\textit{expected}expected：
- 如果expected=Y\textit{expected} = \texttt{Y}expected=Y且observed=N\textit{observed} = \texttt{N}observed=N，则该段在观察时已经损坏（可以从一开始就损坏，也可以是在之前损坏的）。这种情况是允许的。
- 如果expected=N\textit{expected} = \texttt{N}expected=N且observed=Y\textit{observed} = \texttt{Y}observed=Y，则该段在应该灭的时候亮了，这是不可能的（因为段不会在损坏后变亮，也不会从无到有产生亮）。这种情况直接导致不匹配。
- 如果两者相同，则状态一致，无需额外处理。
当某个段在某一时刻被判断为损坏后，在后续的所有显示中，该段只能为N\texttt{N}N（因为损坏的段不会再亮）。如果在后续显示中该段为Y\texttt{Y}Y，则发生矛盾，该起始数字不可行。
搜索策略
由于数字范围很小（000到999），且N≤10N \le 10N≤10，可以采用回溯搜索：
枚举可能的起始数字ddd（从999向下到N−1N-1N−1，或从N−1N-1N−1向上到999）。
对于每个起始数字，尝试匹配整个观察序列：
- 维护一个长度为777的布尔数组broken\textit{broken}broken，记录每个段是否已损坏（初始全为false\texttt{false}false）。
- 对于序列中的第iii个显示（对应数字d−id - id−i）：
- 根据当前数字的编码和broken\textit{broken}broken数组，计算出该显示应有的状态（损坏的段强制为N\texttt{N}N）。
- 将计算出的状态与观察到的状态逐段比较：
- 如果观察为N\texttt{N}N且应为Y\texttt{Y}Y，则该段必须在当前时刻损坏（标记broken[seg]=true\textit{broken}[seg] = \texttt{true}broken[seg]=true）。
- 如果观察为Y\texttt{Y}Y且应为N\texttt{N}N，则矛盾，该起始数字不可行。
- 如果观察为N\texttt{N}N且应为N\texttt{N}N，或观察为Y\texttt{Y}Y且应为Y\texttt{Y}Y，则一致，继续。
- 如果所有NNN个显示都匹配成功，则该序列匹配。
如果存在至少一个起始数字使得匹配成功，输出MATCH\texttt{MATCH}MATCH，否则输出MISMATCH\texttt{MISMATCH}MISMATCH。
复杂度分析
枚举最多101010个起始数字，每个起始数字需要检查N×7N \times 7N×7个段，N≤10N \le 10N≤10，完全可接受。
代码实现
// LED Test// UVa ID: 416// Verdict: Accepted// Submission Date: 2016-07-18// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;map<int,string>led={{0,"YYYYYYN"},{1,"NYYNNNN"},{2,"YYNYYNY"},{3,"YYYYNNY"},{4,"NYYNNYY"},{5,"YNYYNYY"},{6,"YNYYYYY"},{7,"YYYNNNN"},{8,"YYYYYYY"},{9,"YYYYNYY"}};vector<string>segments;intn;boolmatch(intdepth,intdigit,vector<bool>broken){if(depth==n)returntrue;string pattern=segments[depth],displayed=led[digit];for(inti=0;i<7;i++)if(broken[i])displayed[i]='N';for(inti=0;i<7;i++){if(pattern[i]==displayed[i])continue;elseif(pattern[i]=='N'&&displayed[i]=='Y')broken[i]=true;elseif(pattern[i]=='Y'&&displayed[i]=='N')returnfalse;}returnmatch(depth+1,digit-1,broken);}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cin>>n,n){segments.clear();string segment;for(inti=1;i<=n;i++){cin>>segment;segments.push_back(segment);}boolallMatched=false;for(intdigit=n-1;digit<=9;digit++){vector<bool>broken(7,false);string pattern=segments.front(),displayed=led[digit];boolmatched=true;for(inti=0;i<7;i++){if(displayed[i]==pattern[i])continue;elseif(displayed[i]=='Y'&&pattern[i]=='N')broken[i]=true;elseif(displayed[i]=='N'&&pattern[i]=='Y'){matched=false;break;}}if(matched&&match(0,digit,broken)){allMatched=true;break;}}cout<<(allMatched?"MATCH":"MISMATCH")<<'\n';}return0;}
