题目描述每个人的血液中有两个ABO\texttt{ABO}ABO等位基因每个等位基因由A\texttt{A}A、B\texttt{B}B或O\texttt{O}O表示共有六种组合对应四种ABO\texttt{ABO}ABO血型A\texttt{A}A、B\texttt{B}B、AB\texttt{AB}AB、O\texttt{O}O。同时每个人还有两个Rh\texttt{Rh}Rh因子等位基因用和−-−表示。Rh\texttt{Rh}Rh阳性Rh\texttt{Rh}^Rh至少有一个等位基因Rh\texttt{Rh}Rh阴性Rh−\texttt{Rh}^-Rh−必须有两个−-−等位基因。血型是ABO\texttt{ABO}ABO血型与Rh\texttt{Rh}Rh因子的组合写作ABO\texttt{ABO}ABO血型后跟或−-−。子女从父母各继承一个ABO\texttt{ABO}ABO等位基因和一个Rh\texttt{Rh}Rh因子等位基因。给定父母双方的血型或父母一方与子女的血型要求推断另一方父母或子女可能的血型。输入格式输入包含多组测试数据。每组数据一行格式为第一个父母的血型、第二个父母的血型、子女的血型其中父母之一或子女的血型用?代替。血型之间用空格分隔但血型内部不能有空格。输入以一行E N D结束。输出格式对每组测试数据输出Case X:后跟该组数据的血型信息。若推断出的血型集合为空输出IMPOSSIBLE。若集合只有一个元素直接输出该血型。若集合有多个元素按{血型1, 血型2, ...}格式输出顺序不限。样例输入O O- ? O ? O- AB- AB ? AB ? O E N D样例输出Case 1: O O- {O, O-} Case 2: O {A-, A, B-, B, O-, O} O- Case 3: AB- AB {A, A-, B, B-, AB, AB-} Case 4: AB IMPOSSIBLE O题目分析本题要求根据父母和子女的血型信息推断未知血型。血型由ABO\texttt{ABO}ABO等位基因组合和Rh\texttt{Rh}Rh因子组合共同决定。每个人有两个ABO\texttt{ABO}ABO等位基因来自父母各一个和两个Rh\texttt{Rh}Rh因子等位基因。已知的血型可以对应多种基因型例如血型A\texttt{A}A可能对应基因型AA\texttt{AA}AA或AO\texttt{AO}AO血型A\texttt{A}^A可能对应Rh\texttt{Rh}Rh因子基因型或−-−。为了判断两个已知血型的父母能否生出特定血型的子女需要枚举父母所有可能的基因型组合并计算子女所有可能的血型。代码中定义了一个血型到基因型的映射表alleles其中每个血型对应两个数组第一个数组表示两个ABO\texttt{ABO}ABO等位基因第二个数组表示两个Rh\texttt{Rh}Rh因子等位基因。例如血型A对应的ABO\texttt{ABO}ABO等位基因为{A, O}Rh\texttt{Rh}Rh因子等位基因为{, -}。注意对于血型AB\texttt{AB}ABABO\texttt{ABO}ABO等位基因为{A, B}对于血型O\texttt{O}O等位基因为{O, O}对于Rh\texttt{Rh}Rh阴性等位基因为{-, -}。combine函数接收两个血型字符串返回它们所有可能的子女血型集合。函数首先将血型映射到索引k1k1k1和k2k2k2然后枚举父母各自的两个等位基因的所有组合计算子女的ABO\texttt{ABO}ABO基因型。对于ABO\texttt{ABO}ABO基因型将两个等位基因拼接并去重若结果为AO则归一化为A若为BO则归一化为B。对于Rh\texttt{Rh}Rh因子若组合中包含则结果为否则为−-−。最后将ABO\texttt{ABO}ABO血型与Rh\texttt{Rh}Rh因子组合得到所有可能的子女血型。find函数接收一个已知血型b1b1b1和目标血型b2b2b2枚举所有可能的血型bbb若combine(b, b1)的结果包含b2b2b2则bbb是可能的。返回所有满足条件的bbb的集合。这个函数用于推断未知父母的血型。主函数中根据输入中?的位置分三种情况处理若子女为?则直接调用combine计算子女可能血型若第一个父母为?则调用find推断第一个父母若第二个父母为?则调用find推断第二个父母。输出时根据集合大小选择单值、多值或IMPOSSIBLE格式。时间复杂度血型总数只有888种枚举组合非常快每组数据可在常数时间内完成。空间复杂度为O(1)O(1)O(1)用于存储血型和基因型映射。解题思路步骤1\texttt{1}1. 定义血型数组blood包含全部888种血型A、A-、B、B-、AB、AB-、O、O-。步骤2\texttt{2}2. 定义基因型映射表alleles对每种血型给出两个ABO\texttt{ABO}ABO等位基因和两个Rh\texttt{Rh}Rh因子等位基因。例如A对应{{A,O}, {,-}}AB-对应{{A,B}, {-,-}}O对应{{O,O}, {,-}}。步骤3\texttt{3}3. 实现combine(b1, b2)函数找到b1b1b1和b2b2b2在blood中的索引k1k1k1和k2k2k2。枚举i,j∈{0,1}i, j \in \{0, 1\}i,j∈{0,1}从b1b1b1取第iii个ABO\texttt{ABO}ABO等位基因从b2b2b2取第jjj个拼接并去重归一化得到子女的ABO\texttt{ABO}ABO血型。同样枚举Rh\texttt{Rh}Rh因子若含则为否则为−-−。将所有ABO\texttt{ABO}ABO血型与Rh\texttt{Rh}Rh因子组合返回集合。步骤4\texttt{4}4. 实现find(b1, b2)函数枚举所有血型bbb若combine(b, b1)包含b2b2b2则将bbb加入结果集合。返回该集合。步骤5\texttt{5}5. 读取每组数据根据?的位置调用相应函数。若子女为?输出父母血型和combine(parent1, parent2)的结果。若第一个父母为?输出find(parent2, child)的结果、第二个父母和子女。若第二个父母为?输出第一个父母、find(parent1, child)的结果和子女。步骤6\texttt{6}6. 输出格式若集合为空输出IMPOSSIBLE若集合只有一个元素直接输出若多个元素用{...}包裹元素间用,分隔。代码实现// Consanguine Calculations// UVa ID: 1061// Verdict: Accepted// Submission Date: 2017-12-30// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;setstringcombine(string b1,string b2){vectorstringblood{A,A-,B,B-,AB,AB-,O,O-};string alleles[8][2][2]{{{A,O},{,-}},{{A,O},{-,-}},{{B,O},{,-}},{{B,O},{-,-}},{{A,B},{,-}},{{A,B},{-,-}},{{O,O},{,-}},{{O,O},{-,-}},};intk1find(blood.begin(),blood.end(),b1)-blood.begin();intk2find(blood.begin(),blood.end(),b2)-blood.begin();setstringabo;for(inti0;i2;i)for(intj0;j2;j){string factoralleles[k1][0][i]alleles[k2][0][j];sort(factor.begin(),factor.end());factor.erase(unique(factor.begin(),factor.end()),factor.end());if(factorAO)factorA;if(factorBO)factorB;abo.insert(factor);}setstringrh;for(inti0;i2;i)for(intj0;j2;j){string factoralleles[k1][1][i]alleles[k2][1][j];if(factor.find()!factor.npos)factor;elsefactor-;rh.insert(factor);}setstringr;for(autoa1:abo)for(autoa2:rh)r.insert(a1a2);returnr;}setstringfind(string b1,string b2){vectorstringblood{A,A-,B,B-,AB,AB-,O,O-};setstringr;for(autob:blood)if(combine(b,b1).count(b2)0)r.insert(b);returnr;}voidprint(setstringr){if(r.size()0)coutIMPOSSIBLE;else{if(r.size()1)cout*r.begin();else{cout{;intcnt0;for(autob:r){if(cnt0)cout, ;coutb;}cout};}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string parent1,parent2,child;intcases0;while(cinparent1parent2child){if(parent1E)break;coutCase cases:;if(child?){cout parent1 parent2 ;print(combine(parent1,parent2));cout\n;}else{if(parent1?){cout ;print(find(parent2,child));cout parent2 child\n;}else{cout parent1 ;print(find(parent1,child));cout child\n;}}}return0;}总结本题的核心是根据血型遗传规律推断未知血型。通过枚举父母所有可能的基因型组合计算子女可能出现的血型可以解决正向推断已知父母求子女和反向推断已知一方父母和子女求另一方父母两类问题。血型总数只有888种枚举空间极小算法简洁高效。输出格式需要根据可能血型集合的大小灵活处理空集输出IMPOSSIBLE单元素直接输出多元素用花括号包裹。该解法充分利用了题目规模小的特点逻辑清晰易于实现。