UVA340 猜数字游戏的提示 Master-Mind Hints题目描述PDF输入格式输出格式输入输出样例 #1输入 #14 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输出 #1Game 1: (1,1) (2,0) (1,2) (1,2) (4,0) Game 2: (2,4) (3,2) (5,0) (7,0)题目大意MasterMind 是一个双人游戏。其中一名玩家 “设计者” 选定一串密码另一名玩家 “破译者” 尝试破解密码。密码是一排彩色圆点。游戏开局时双方约定好密码的长度 N 以及可用的颜色种类。破译者会多次给出猜测串每一轮猜测结束后设计者会给出提示说明本次猜测和真实密码的匹配程度。本题给定真实密码s₁…sₙ和猜测串g₁…gₙ要求计算对应的提示信息。匹配规则定义如下一对下标(i,j)满足sᵢ gⱼ就构成一次匹配。当ij时这是强匹配否则为弱匹配。两组匹配(i,j)和(p,q)互相独立的条件是ip和jq必须同时成立。一个匹配集合里任意两组匹配都互相独立就称这个集合是独立匹配集。设计者要选出一个独立匹配集 M使得集合内总匹配数尽可能大同时强匹配的数量也要尽可能大。最终提示由集合 M 里强匹配数量在前、弱匹配数量在后组成这两个数值是唯一确定的。如果提示为(n,0)说明猜测串和密码完全一致。输入格式输入包含多组游戏数据。每组游戏以整数 N密码长度开头紧接着是由 N 个 1~9 整数组成的真实密码。之后会有多组猜测串每组猜测串同样是 N 个 1~9 的整数。每组游戏的最后一行是 N 个 0这一行不作为猜测串。一组游戏结束后会继续下一组游戏如果还有数据下一组依然以新的 N 开头。当单独输入一个 0 时代表所有游戏输入结束。N 的最大取值为 1000。输出格式按顺序输出每组猜测对应的提示每行一条。提示用括号包裹两个整数中间用逗号隔开。每组游戏的输出开头要打印游戏编号游戏从 1 开始顺序编号严格参照样例格式输出。解题思路先算出强匹配的数量逐个位置对照密码和猜测串如果下标相同并且数字一致就给强匹配计数加一同时把这两个位置标记成已经占用不让它们再参与后面弱匹配的计算。找弱匹配时把两边剩下还没被占用的数字分别统计好每个数字出现了多少次对于每一个数字能形成弱匹配的对数就取两边数量里的小值把所有数字的匹配数量加在一起最终得到弱匹配总数。完整代码importjava.util.Scanner;publicclassMasterMindHints{publicstaticvoidmain(Stringargs[]){ScannerscnewScanner(System.in);intgame1;while(true){intnsc.nextInt();if(n0){break;}int[]passwordnewint[n];for(inti0;in;i){password[i]sc.nextInt();}System.out.println(Game game:);game;while(true){int[]guessnewint[n];booleanendLinetrue;for(inti0;in;i){guess[i]sc.nextInt();if(guess[i]!0){endLinefalse;}}if(endLine){break;}intstrong0;boolean[]pasnewboolean[n];boolean[]guenewboolean[n];for(inti0;in;i){if(password[i]guess[i]){strong;pas[i]true;gue[i]true;}}int[]passnewint[10];int[]guesnewint[10];for(inti0;in;i){if(!pas[i]){pass[password[i]];}}for(inti0;in;i){if(!gue[i]){gues[guess[i]];}}intweak0;for(inti1;i9;i){weakweakMath.min(pass[i],gues[i]);}System.out.println((strong,weak));}}sc.close();}}