UVa 777 Codebreakers

题目描述Alice\texttt{Alice}Alice和Bob\texttt{Bob}Bob使用一个密钥即一串密码进行私密通信。该密钥是从字符集SSS大小为nnn中选出的mmm个互不相同的字符所组成的有序序列。例如若S{1,2,3,4,5,6,7,8,9}S\{1,2,3,4,5,6,7,8,9\}S{1,2,3,4,5,6,7,8,9}且m4m4m4则一个可能的密钥是(3,8,1,5)(3,8,1,5)(3,8,1,5)。除Alice\texttt{Alice}Alice和Bob\texttt{Bob}Bob外无人知晓密钥。然而间谍Steve\texttt{Steve}Steve知道集合SSS和密钥长度mmm他试图通过提交不同的猜测来推出密钥。每次猜测都会收到一个形如(c,w)(c,w)(c,w)的答复其中ccc表示猜测中位置正确的数字个数www表示猜测中存在于密钥中但位置错误的数字个数即错位数。例如对于上述密钥有以下猜测与答复(1,1,1,1)→(1,0),(2,2,2,2)→(0,0),(9,8,3,1)→(1,2) (1,1,1,1)\rightarrow (1,0),\quad (2,2,2,2)\rightarrow (0,0),\quad (9,8,3,1)\rightarrow (1,2)(1,1,1,1)→(1,0),(2,2,2,2)→(0,0),(9,8,3,1)→(1,2)注意正确的猜测会得到答复(m,0)(m,0)(m,0)。给定SSS、mmm以及若干条任意长度猜测‑答复记录程序需要执行以下操作之一宣称给定信息不足以唯一确定正确密钥或给出正确的密钥即那个能得到答复(m,0)(m,0)(m,0)的密钥。输入格式输入文件包含多个测试用例每个测试用例描述如下n≤10, m≤nn\le 10,\; m\le nn≤10,m≤n第一行给出集合SSS元素之间以空格分隔不含括号。第二行给出整数mmm。接下来若干行每行为一条猜测‑答复格式为⟨g1,…,gm⟩→⟨c,w⟩\langle g_1,\ldots,g_m\rangle \rightarrow \langle c,w\rangle⟨g1​,…,gm​⟩→⟨c,w⟩其中gi∈Sg_i\in Sgi​∈S。每个测试用例以单独一行字符%结束。输出格式对于每个测试用例输出一行若存在唯一满足所有记录的密钥则按格式⟨s1,…,sm⟩\langle s_1,\ldots,s_m\rangle⟨s1​,…,sm​⟩输出该密钥否则输出大写字母N。样例输入123456789 3 (1,1,1)-(0,0) (2,2,2)-(0,0) (3,3,3)-(0,0) (4,4,4)-(1,0) (5,5,5)-(0,0) (6,6,6)-(0,0) (7,7,7)-(1,0) (8,8,8)-(1,0) (4,7,8)-(1,2) (4,8,7)-(0,3) (8,7,4)-(0,3) (7,8,4)-(1,2) (8,4,7)-(1,2) % 123456789 3 (1,1,1)-(0,0) (2,2,2)-(0,0) (3,3,3)-(0,0) (4,4,4)-(1,0) (5,5,5)-(0,0) (6,6,6)-(0,0) (7,7,7)-(1,0) (8,8,8)-(1,0) (9,9,9)-(0,0) %输出(7,4,8) N题目分析本题是经典的Mastermind\texttt{Mastermind}Mastermind猜数字变种。密钥中的字符必须互不相同且所有字符都属于已知集合SSS。给定若干次猜测以及对应的(c,w)(c,w)(c,w)反馈我们需要判断能否唯一确定密钥。最直接的思路是枚举所有可能的密钥并逐一检查是否与所有已知反馈一致。密钥总数等于从nnn个元素中选取mmm个不同元素的排列数P(n,m)n!(n−m)! P(n,m)\frac{n!}{(n-m)!}P(n,m)(n−m)!n!​由于题目限制n≤10n\le 10n≤10最大情况n10,m10n10,m10n10,m10时P(10,10)10!3 628 800P(10,10)10! 3\,628\,800P(10,10)10!3628800在可接受范围内。即使存在多条猜测记录每条记录长度mmm验证一个密钥的代价为O(m⋅g)O(m\cdot g)O(m⋅g)其中ggg为猜测条数。最坏情况下总运算量约为3.6×106×10×g3.6\times 10^6 \times 10 \times g3.6×106×10×g若ggg也较大可能略高但实际输入规模下完全可行。因此采用暴力枚举所有排列并逐条验证的方法简单可靠且无需复杂数据结构。解题思路1. 枚举所有合法密钥集合SSS中字符互不相同密钥要求mmm个位置上的字符也互不相同因此合法密钥就是SSS中取mmm个元素的全排列。使用深度优先搜索DFS\texttt{DFS}DFS生成所有排列同时记录当前已用字符避免重复。2. 验证候选密钥对于每个生成的排列key\textit{key}key依次与每一条猜测记录比较计算该猜测对应的(c,w)(c,w)(c,w)并与记录值比对。计算规则如下正确位置数ccc逐位比较key[i]\textit{key}[i]key[i]与猜测guess[i]\textit{guess}[i]guess[i]相同则ccc加111。错位数www首先统计key\textit{key}key和猜测中每个字符出现的次数取逐字符次数最小值求和得到两个序列中共同字符的总数total\textit{total}total。由于共同字符中包含了位置正确的那些因此错位数wtotal−cw \textit{total} - cwtotal−c。若所有记录均匹配则该key\textit{key}key是一个可行解。3. 判断唯一性枚举过程中维护一个解列表。若发现第二个可行解即可提前终止枚举因为此时不可能唯一确定输出N。枚举结束后若解列表为空说明输入数据自相矛盾实际不会出现因为真实密钥一定满足所有记录也输出N若恰好一个解则输出该解。4. 输入解析每一条猜测‑答复的格式为(g1,g2,...,gm)-(c,w)其中可能包含多余空格。处理时先去除所有空白字符再按箭头-分割左右部分最后解析括号内的逗号分隔数值。复杂度分析枚举排列数O(P(n,m))O(P(n,m))O(P(n,m))。每个排列验证O(g⋅m)O(g \cdot m)O(g⋅m)其中ggg为猜测条数。总时间复杂度O(P(n,m)⋅g⋅m)O(P(n,m) \cdot g \cdot m)O(P(n,m)⋅g⋅m)。由于n≤10n\le 10n≤10该上界在实际数据中足够小。空间复杂度O(g⋅m)O(g \cdot m)O(g⋅m)用于存储猜测记录以及递归栈深度O(m)O(m)O(m)。代码实现// Codebreakers// UVa ID: 777// Verdict: Accepted// Submission Date: 2026-07-08// UVa Run Time: 2.150s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 存储单条猜测及其答复structGuess{vectorcharg;// 猜测序列intc,w;// 正确位置数、错位数};// 解析一行猜测‑答复填充 Guess 结构voidparseLine(conststringline,intm,Guessguess){string s;for(charch:line)if(!isspace(ch))s.push_back(ch);// 移除所有空白字符size_t arrows.find(-);string lefts.substr(0,arrow);string rights.substr(arrow2);// 去掉左右括号leftleft.substr(1,left.size()-2);rightright.substr(1,right.size()-2);// 解析猜测序列逗号分隔stringstreamss1(left);string token;while(getline(ss1,token,,)){if(!token.empty())guess.g.push_back(token[0]);}// 解析 c 和 wstringstreamss2(right);vectorintnums;while(getline(ss2,token,,)){nums.push_back(stoi(token));}guess.cnums[0];guess.wnums[1];}// 检查候选密钥是否满足所有猜测boolcheckKey(constvectorcharkey,constvectorGuessguesses){intmkey.size();for(constautoguess:guesses){intc0,w0;// 计算正确位置数for(inti0;im;i)if(key[i]guess.g[i])c;// 统计密钥和猜测中各字符出现次数intcntKey[256]{0},cntGuess[256]{0};for(charch:key)cntKey[(unsignedchar)ch];for(charch:guess.g)cntGuess[(unsignedchar)ch];// 共同字符总数inttotal0;for(inti0;i256;i)totalmin(cntKey[i],cntGuess[i]);wtotal-c;// 错位数 共同总数 - 正确位置数if(c!guess.c||w!guess.w)returnfalse;}returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string line;while(getline(cin,line)){// 跳过空行if(line.empty())continue;// 读取字符集 SvectorcharS;for(charch:line)if(!isspace(ch))S.push_back(ch);// 读取 mgetline(cin,line);while(line.empty())getline(cin,line);intmstoi(line);// 读取所有猜测记录vectorGuessguesses;while(true){getline(cin,line);if(line.empty())continue;// 去除行首空白size_t startline.find_first_not_of( \t);if(startstring::npos)continue;lineline.substr(start);if(line[0]%)break;Guess g;parseLine(line,m,g);guesses.push_back(g);}// 枚举所有排列回溯vectorvectorcharsolutions;vectorboolused(S.size(),false);vectorcharcur;functionvoid()dfs[](){if(cur.size()(size_t)m){if(checkKey(cur,guesses))solutions.push_back(cur);return;}for(size_t i0;iS.size();i){if(!used[i]){used[i]true;cur.push_back(S[i]);dfs();cur.pop_back();used[i]false;// 若已找到两个可行解无需继续枚举if(solutions.size()1)return;}}};dfs();if(solutions.size()1){cout(;for(inti0;im;i){if(i)cout,;coutsolutions[0][i];}cout)\n;}else{coutN\n;}}return0;}总结本题的核心在于利用nnn很小的特点直接枚举所有可能的排列并逐条验证反馈。这种暴力方法实现简单不易出错且在当前数据规模下完全可行。关键点密钥中字符互不相同因此枚举时需使用排列而非组合并利用回溯保证不重复。计算(c,w)(c,w)(c,w)时错位数www需先求出共同字符总数再减去正确位置数不能直接统计错位字符个数因为存在重复字符时统计方法不同。提前终止枚举找到第二个可行解可显著减少无用计算。该解法的时间复杂度虽为指数级但受限于n≤10n\le 10n≤10运行效率尚可可在时限内通过是解决此类小规模约束问题的经典策略。