题目描述Master Mind\texttt{Master Mind}Master Mind是一种猜颜色组合的游戏。秘密代码是一个由若干颜色组成的序列玩家通过猜测并获得反馈反馈包含两个数字第一个是颜色和位置都正确的个数第二个是颜色正确但位置错误的个数。本题中颜色用数字111到999表示秘密代码的长度与猜测长度相同范围为222到555。给定一个猜测及其反馈要求计算有多少种可能的秘密代码能够产生该反馈。输入格式第一行包含一个整数NNN1≤N≤301 \le N \le 301≤N≤30表示测试用例数量。随后NNN行每行包含一个测试用例由三部分组成以空格分隔首先是猜测字符串由数字111到999组成长度222到555然后是反馈中的两个整数分别表示颜色和位置都正确的个数以及颜色正确但位置错误的个数。输出格式对于每个测试用例输出一行一个整数表示能够产生该反馈的可能秘密代码数量。注意颜色总数始终为999秘密代码长度必须等于猜测长度。样例输入5 1234 2 2 111 1 0 567 0 1 91543 5 0 91543 0 5样例输出6 192 234 1 44题目分析本题要求统计与给定猜测和反馈一致的所有可能秘密代码数量。由于颜色总数为999代码长度为222到555所有可能的秘密代码总数为9293949581729656159049664209^2 9^3 9^4 9^5 81 729 6561 59049 66420929394958172965615904966420规模较小可以预先枚举所有可能的代码然后对每个查询逐一比对。反馈的计算规则为首先统计颜色和位置都正确的个数然后将这些位置从猜测和秘密代码中同时移除接着统计颜色正确但位置错误的个数即对于猜测中剩余的每个颜色若秘密代码中剩余部分存在相同颜色则计数加一并移除该颜色。最终比较计算得到的反馈与给定反馈是否一致。解题思路首先使用深度优先搜索预生成所有长度从222到555的秘密代码存储在二维向量secret中其中secret[length]存储所有长度为length的代码。由于颜色用数字111到999表示每个位置有999种选择递归生成即可。对于每个测试用例读取猜测字符串guess和反馈值right、wrong。遍历secret[guess.length()]中的所有候选代码对每个候选代码调用match函数判断其反馈是否与给定值一致。match函数首先统计位置和颜色都正确的个数然后将这些位置在猜测和候选代码中标记为已使用例如置为字符0。接着统计颜色正确但位置错误的个数遍历猜测中未使用的位置在候选代码中查找相同颜色若找到则计数加一并将候选代码中该位置标记为已使用。最后返回统计结果是否与给定反馈相等。若匹配成功计数器加一。输出计数器的值即为答案。预处理阶段生成所有代码的时间复杂度为O(95)O(9^5)O(95)每个测试用例的匹配时间复杂度为O(9L×L2)O(9^L \times L^2)O(9L×L2)其中LLL为代码长度最大为555。总时间复杂度在题目规模下完全可行。代码实现// Master Mind Helper// UVa ID: 947// Verdict: Accepted// Submission Date: 2017-03-13// UVa Run Time: 0.070s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorvectorstringsecret(6);voiddfs(string code,intlength){if(length5)return;for(inti1;i9;i){string nextcode(char)(0i);secret[length].push_back(next);dfs(next,length1);}}boolmatch(string answer,string guess,intright,intwrong){intr0,w0;for(inti0;ianswer.length();i)if(answer[i]guess[i]){r;guess[i]0;answer[i]0;}for(inti0;iguess.length();i)for(intj0;janswer.length();j)if(guess[i]!0guess[i]answer[j]){w;answer[j]0;break;}returnrightrwrongw;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);dfs(,1);string guess;intright,wrong;intcases;cincases;for(intc1;ccases;c){cinguessrightwrong;intcount0;for(autoanswer:secret[guess.length()])if(match(answer,guess,right,wrong))count;coutcount\n;}return0;}总结本题的关键在于正确实现反馈的计算逻辑特别是处理重复颜色时的计数方式。在统计颜色正确但位置错误的个数时必须确保每个位置的颜色只被匹配一次。通过预生成所有可能的秘密代码可以快速响应每个查询。时间复杂度为O(95N×9L×L2)O(9^5 N \times 9^L \times L^2)O(95N×9L×L2)空间复杂度为O(95)O(9^5)O(95)在题目给定规模下能够高效运行。
UVa 947 Master Mind Helper
题目描述Master Mind\texttt{Master Mind}Master Mind是一种猜颜色组合的游戏。秘密代码是一个由若干颜色组成的序列玩家通过猜测并获得反馈反馈包含两个数字第一个是颜色和位置都正确的个数第二个是颜色正确但位置错误的个数。本题中颜色用数字111到999表示秘密代码的长度与猜测长度相同范围为222到555。给定一个猜测及其反馈要求计算有多少种可能的秘密代码能够产生该反馈。输入格式第一行包含一个整数NNN1≤N≤301 \le N \le 301≤N≤30表示测试用例数量。随后NNN行每行包含一个测试用例由三部分组成以空格分隔首先是猜测字符串由数字111到999组成长度222到555然后是反馈中的两个整数分别表示颜色和位置都正确的个数以及颜色正确但位置错误的个数。输出格式对于每个测试用例输出一行一个整数表示能够产生该反馈的可能秘密代码数量。注意颜色总数始终为999秘密代码长度必须等于猜测长度。样例输入5 1234 2 2 111 1 0 567 0 1 91543 5 0 91543 0 5样例输出6 192 234 1 44题目分析本题要求统计与给定猜测和反馈一致的所有可能秘密代码数量。由于颜色总数为999代码长度为222到555所有可能的秘密代码总数为9293949581729656159049664209^2 9^3 9^4 9^5 81 729 6561 59049 66420929394958172965615904966420规模较小可以预先枚举所有可能的代码然后对每个查询逐一比对。反馈的计算规则为首先统计颜色和位置都正确的个数然后将这些位置从猜测和秘密代码中同时移除接着统计颜色正确但位置错误的个数即对于猜测中剩余的每个颜色若秘密代码中剩余部分存在相同颜色则计数加一并移除该颜色。最终比较计算得到的反馈与给定反馈是否一致。解题思路首先使用深度优先搜索预生成所有长度从222到555的秘密代码存储在二维向量secret中其中secret[length]存储所有长度为length的代码。由于颜色用数字111到999表示每个位置有999种选择递归生成即可。对于每个测试用例读取猜测字符串guess和反馈值right、wrong。遍历secret[guess.length()]中的所有候选代码对每个候选代码调用match函数判断其反馈是否与给定值一致。match函数首先统计位置和颜色都正确的个数然后将这些位置在猜测和候选代码中标记为已使用例如置为字符0。接着统计颜色正确但位置错误的个数遍历猜测中未使用的位置在候选代码中查找相同颜色若找到则计数加一并将候选代码中该位置标记为已使用。最后返回统计结果是否与给定反馈相等。若匹配成功计数器加一。输出计数器的值即为答案。预处理阶段生成所有代码的时间复杂度为O(95)O(9^5)O(95)每个测试用例的匹配时间复杂度为O(9L×L2)O(9^L \times L^2)O(9L×L2)其中LLL为代码长度最大为555。总时间复杂度在题目规模下完全可行。代码实现// Master Mind Helper// UVa ID: 947// Verdict: Accepted// Submission Date: 2017-03-13// UVa Run Time: 0.070s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorvectorstringsecret(6);voiddfs(string code,intlength){if(length5)return;for(inti1;i9;i){string nextcode(char)(0i);secret[length].push_back(next);dfs(next,length1);}}boolmatch(string answer,string guess,intright,intwrong){intr0,w0;for(inti0;ianswer.length();i)if(answer[i]guess[i]){r;guess[i]0;answer[i]0;}for(inti0;iguess.length();i)for(intj0;janswer.length();j)if(guess[i]!0guess[i]answer[j]){w;answer[j]0;break;}returnrightrwrongw;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);dfs(,1);string guess;intright,wrong;intcases;cincases;for(intc1;ccases;c){cinguessrightwrong;intcount0;for(autoanswer:secret[guess.length()])if(match(answer,guess,right,wrong))count;coutcount\n;}return0;}总结本题的关键在于正确实现反馈的计算逻辑特别是处理重复颜色时的计数方式。在统计颜色正确但位置错误的个数时必须确保每个位置的颜色只被匹配一次。通过预生成所有可能的秘密代码可以快速响应每个查询。时间复杂度为O(95N×9L×L2)O(9^5 N \times 9^L \times L^2)O(95N×9L×L2)空间复杂度为O(95)O(9^5)O(95)在题目给定规模下能够高效运行。
