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​，需要确定提示。提示由一对数字确定：

• 强匹配：si=gjs_i = g_jsi​=gj​且i=ji = ji=j
• 弱匹配：si=gjs_i = g_jsi​=gj​且i≠ji \neq ji=j

设计者选择一组独立匹配（即每个位置最多被使用一次），使得强匹配和弱匹配的数量都最大。提示由强匹配数后跟弱匹配数组成。

如果提示是(n,0)(n,0)(n,0)，则猜测与秘密代码完全相同。

输入格式

输入包含多场游戏的数据。每场游戏以一个整数NNN（代码长度）开始，然后是秘密代码（NNN个整数，范围111到999）。接着是任意数量的猜测，每个猜测也是NNN个整数（范围111到999）。每场游戏的最后一个猜测后跟NNN个000（这些000不应视为猜测）。

第一场游戏之后是第二场游戏的数据（以新的NNN开始）。输入的最后一场游戏后跟一个单独的000（即N=0N=0N=0）。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

统计频率：

weak = 1

提示：(1,1)

参考代码

// Master-Mind Hints// UVa ID: 340// Verdict: Accepted// Submission Date: 2016-06-27// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){intsecret[1100],guess[1100],n,cases=0;while(cin>>n,n){// 读取秘密代码for(inti=1;i<=n;i++)cin>>secret[i];cout<<"Game "<<++cases<<":"<<endl;// 处理猜测while(true){intstrong=0;// 统计强匹配，同时收集未匹配的数字频率map<int,int>S,G;for(inti=1;i<=n;i++){cin>>guess[i];if(secret[i]==guess[i])strong++;else{S[secret[i]]++;G[guess[i]]++;}}// 猜测结束标志：第一个数字为 0if(guess[1]==0)break;// 计算弱匹配intweak=0;for(auto&p:S)if(G.find(p.first)!=G.end())weak+=min(p.second,G[p.first]);cout<<" ("<<strong<<","<<weak<<")"<<endl;}}return0;}