题目描述MasterMind\texttt{MasterMind}MasterMind是一个双人游戏。其中一方是设计者选择一组秘密代码。另一方是破解者试图破解它。代码只是一行彩色点。在游戏开始时玩家约定代码的长度NNN以及代码中可能出现的颜色。为了破解代码破解者进行多次猜测每次猜测本身也是一个代码。每次猜测后设计者给出一个提示说明猜测与秘密代码的匹配程度。在本题中给定一个秘密代码s1,s2,…,sns_1, s_2, \dots, s_ns1,s2,…,sn和一个猜测代码g1,g2,…,gng_1, g_2, \dots, g_ng1,g2,…,gn需要确定提示。提示由一对数字确定强匹配sigjs_i g_jsigj且iji jij弱匹配sigjs_i g_jsigj且i≠ji \neq jij设计者选择一组独立匹配即每个位置最多被使用一次使得强匹配和弱匹配的数量都最大。提示由强匹配数后跟弱匹配数组成。如果提示是(n,0)(n,0)(n,0)则猜测与秘密代码完全相同。输入格式输入包含多场游戏的数据。每场游戏以一个整数NNN代码长度开始然后是秘密代码NNN个整数范围111到999。接着是任意数量的猜测每个猜测也是NNN个整数范围111到999。每场游戏的最后一个猜测后跟NNN个000这些000不应视为猜测。第一场游戏之后是第二场游戏的数据以新的NNN开始。输入的最后一场游戏后跟一个单独的000即N0N0N0。NNN的最大值为100010001000。输出格式对于每场游戏输出游戏编号然后按顺序为每个猜测输出一行提示。每个提示表示为(strong,weak)。格式如样例所示。样例输入4 1 3 5 5 1 1 2 3 4 3 3 5 6 5 5 1 6 1 3 5 1 3 5 5 0 0 0 0 10 1 2 2 2 4 5 6 6 6 9 1 2 3 4 5 6 7 8 9 1 1 1 2 2 3 3 4 4 5 5 1 2 1 3 1 5 1 6 1 9 1 2 2 5 5 5 6 6 6 7 0 0 0 0 0 0 0 0 0 0 0样例输出Game 1: (1,1) (2,0) (1,2) (1,2) (4,0) Game 2: (2,4) (3,2) (5,0) (7,0)题目分析问题的本质这是一个匹配计数问题。给定两个等长的序列sss和ggg需要计算强匹配数相同位置上数值相等的个数弱匹配数不同位置上数值相等的个数每个数值最多被计数一次算法描述计算强匹配很简单直接遍历所有位置统计secret[i] guess[i]的数量。对于弱匹配需要处理剩余的数字排除已匹配的强匹配位置。对于每个数值vvv它在秘密代码中剩余的个数为count_secret[v]在猜测代码中剩余的个数为count_guess[v]。弱匹配数为所有vvv的min(count_secret[v], count_guess[v])之和。示例说明以第一个示例的第一组数据为例秘密代码1 3 5 5猜测代码1 1 2 3强匹配位置111都是111所以strong 1剩余数字秘密剩余3, 5, 5猜测剩余1, 2, 3统计频率数值秘密剩余次数猜测剩余次数min1010201031115200weak 1提示(1,1)参考代码// Master-Mind Hints// UVa ID: 340// Verdict: Accepted// Submission Date: 2016-06-27// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){intsecret[1100],guess[1100],n,cases0;while(cinn,n){// 读取秘密代码for(inti1;in;i)cinsecret[i];coutGame cases:endl;// 处理猜测while(true){intstrong0;// 统计强匹配同时收集未匹配的数字频率mapint,intS,G;for(inti1;in;i){cinguess[i];if(secret[i]guess[i])strong;else{S[secret[i]];G[guess[i]];}}// 猜测结束标志第一个数字为 0if(guess[1]0)break;// 计算弱匹配intweak0;for(autop:S)if(G.find(p.first)!G.end())weakmin(p.second,G[p.first]);cout (strong,weak)endl;}}return0;}
UVa 340 Master-Mind Hints
题目描述MasterMind\texttt{MasterMind}MasterMind是一个双人游戏。其中一方是设计者选择一组秘密代码。另一方是破解者试图破解它。代码只是一行彩色点。在游戏开始时玩家约定代码的长度NNN以及代码中可能出现的颜色。为了破解代码破解者进行多次猜测每次猜测本身也是一个代码。每次猜测后设计者给出一个提示说明猜测与秘密代码的匹配程度。在本题中给定一个秘密代码s1,s2,…,sns_1, s_2, \dots, s_ns1,s2,…,sn和一个猜测代码g1,g2,…,gng_1, g_2, \dots, g_ng1,g2,…,gn需要确定提示。提示由一对数字确定强匹配sigjs_i g_jsigj且iji jij弱匹配sigjs_i g_jsigj且i≠ji \neq jij设计者选择一组独立匹配即每个位置最多被使用一次使得强匹配和弱匹配的数量都最大。提示由强匹配数后跟弱匹配数组成。如果提示是(n,0)(n,0)(n,0)则猜测与秘密代码完全相同。输入格式输入包含多场游戏的数据。每场游戏以一个整数NNN代码长度开始然后是秘密代码NNN个整数范围111到999。接着是任意数量的猜测每个猜测也是NNN个整数范围111到999。每场游戏的最后一个猜测后跟NNN个000这些000不应视为猜测。第一场游戏之后是第二场游戏的数据以新的NNN开始。输入的最后一场游戏后跟一个单独的000即N0N0N0。NNN的最大值为100010001000。输出格式对于每场游戏输出游戏编号然后按顺序为每个猜测输出一行提示。每个提示表示为(strong,weak)。格式如样例所示。样例输入4 1 3 5 5 1 1 2 3 4 3 3 5 6 5 5 1 6 1 3 5 1 3 5 5 0 0 0 0 10 1 2 2 2 4 5 6 6 6 9 1 2 3 4 5 6 7 8 9 1 1 1 2 2 3 3 4 4 5 5 1 2 1 3 1 5 1 6 1 9 1 2 2 5 5 5 6 6 6 7 0 0 0 0 0 0 0 0 0 0 0样例输出Game 1: (1,1) (2,0) (1,2) (1,2) (4,0) Game 2: (2,4) (3,2) (5,0) (7,0)题目分析问题的本质这是一个匹配计数问题。给定两个等长的序列sss和ggg需要计算强匹配数相同位置上数值相等的个数弱匹配数不同位置上数值相等的个数每个数值最多被计数一次算法描述计算强匹配很简单直接遍历所有位置统计secret[i] guess[i]的数量。对于弱匹配需要处理剩余的数字排除已匹配的强匹配位置。对于每个数值vvv它在秘密代码中剩余的个数为count_secret[v]在猜测代码中剩余的个数为count_guess[v]。弱匹配数为所有vvv的min(count_secret[v], count_guess[v])之和。示例说明以第一个示例的第一组数据为例秘密代码1 3 5 5猜测代码1 1 2 3强匹配位置111都是111所以strong 1剩余数字秘密剩余3, 5, 5猜测剩余1, 2, 3统计频率数值秘密剩余次数猜测剩余次数min1010201031115200weak 1提示(1,1)参考代码// Master-Mind Hints// UVa ID: 340// Verdict: Accepted// Submission Date: 2016-06-27// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){intsecret[1100],guess[1100],n,cases0;while(cinn,n){// 读取秘密代码for(inti1;in;i)cinsecret[i];coutGame cases:endl;// 处理猜测while(true){intstrong0;// 统计强匹配同时收集未匹配的数字频率mapint,intS,G;for(inti1;in;i){cinguess[i];if(secret[i]guess[i])strong;else{S[secret[i]];G[guess[i]];}}// 猜测结束标志第一个数字为 0if(guess[1]0)break;// 计算弱匹配intweak0;for(autop:S)if(G.find(p.first)!G.end())weakmin(p.second,G[p.first]);cout (strong,weak)endl;}}return0;}
