题目描述
Master Mind\texttt{Master Mind}Master Mind是一种猜颜色组合的游戏。秘密代码是一个由若干颜色组成的序列，玩家通过猜测并获得反馈：反馈包含两个数字，第一个是颜色和位置都正确的个数，第二个是颜色正确但位置错误的个数。本题中，颜色用数字111到999表示，秘密代码的长度与猜测长度相同，范围为222到555。给定一个猜测及其反馈，要求计算有多少种可能的秘密代码能够产生该反馈。
输入格式
第一行包含一个整数NNN（1≤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，所有可能的秘密代码总数为92+93+94+95=81+729+6561+59049=664209^2 + 9^3 + 9^4 + 9^5 = 81 + 729 + 6561 + 59049 = 6642092+93+94+95=81+729+6561+59049=66420，规模较小，可以预先枚举所有可能的代码，然后对每个查询逐一比对。
反馈的计算规则为：首先统计颜色和位置都正确的个数，然后将这些位置从猜测和秘密代码中同时移除；接着统计颜色正确但位置错误的个数，即对于猜测中剩余的每个颜色，若秘密代码中剩余部分存在相同颜色，则计数加一，并移除该颜色。最终比较计算得到的反馈与给定反馈是否一致。
解题思路
首先使用深度优先搜索预生成所有长度从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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<vector<string>>secret(6);voiddfs(string code,intlength){if(length>5)return;for(inti=1;i<=9;i++){string next=code+(char)('0'+i);secret[length].push_back(next);dfs(next,length+1);}}boolmatch(string answer,string guess,intright,intwrong){intr=0,w=0;for(inti=0;i<answer.length();i++)if(answer[i]==guess[i]){r++;guess[i]='0';answer[i]='0';}for(inti=0;i<guess.length();i++)for(intj=0;j<answer.length();j++)if(guess[i]!='0'&&guess[i]==answer[j]){w++;answer[j]='0';break;}returnright==r&&wrong==w;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);dfs("",1);string guess;intright,wrong;intcases;cin>>cases;for(intc=1;c<=cases;c++){cin>>guess>>right>>wrong;intcount=0;for(autoanswer:secret[guess.length()])if(match(answer,guess,right,wrong))count++;cout<<count<<'\n';}return0;}总结
本题的关键在于正确实现反馈的计算逻辑，特别是处理重复颜色时的计数方式。在统计颜色正确但位置错误的个数时，必须确保每个位置的颜色只被匹配一次。通过预生成所有可能的秘密代码，可以快速响应每个查询。时间复杂度为O(95+N×9L×L2)O(9^5 + N \times 9^L \times L^2)O(95+N×9L×L2)，空间复杂度为O(95)O(9^5)O(95)，在题目给定规模下能够高效运行。
)
