UVa 653 Gizilch

题目描述游戏“Gizilch\texttt{Gizilch}Gizilch”的规则很简单有100100100颗葡萄分别标有编号111到100100100。两名玩家的初始得分均为111他们比赛吃葡萄每吃一颗葡萄就将自己的得分乘以该葡萄的编号。一分钟后剩余葡萄被松鼠吃掉玩家报告自己的最终得分即所吃葡萄编号的乘积。得分较高者被认为是非正式胜者但官方胜者需要经过质疑。得分较低的玩家有权质疑对手的得分且假定低分者说真话因为若他说谎他会编造一个更大的分数。如果高分者的得分无法通过未被他质疑玩家吃掉的葡萄得到则挑战成功低分者获胜。给定两个不相等的正整数字符表示两个玩家声称的得分。要求输出官方胜者的得分。输入格式输入包含若干行每行两个不相等的正整数表示两个玩家的得分。输出格式对于每一对得分输出一行即官方胜者的得分。样例输入343 49 3599 610 62 36输出49 610 62题目分析本题的核心是判断两个得分是否可以被两组互不重复的葡萄编号111到100100100通过乘积表示。如果存在这样的两组分解则两人均可说真话高分者获胜如果低分者无法被任何合法分解表示则低分者肯定说谎高分者获胜否则低分者可表示但高分者无法表示或与低分者所有分解都冲突则低分者获胜。更形式化地设低分aaa高分bbb。令F(x)F(x)F(x)为将xxx分解为111到100100100之间的互不相同的整数因子的乘积的所有可能集合每个集合中的因子按升序排列。若F(a)∅F(a) \emptysetF(a)∅则aaa不可能实现输出bbb。否则若F(b)∅F(b) \emptysetF(b)∅则bbb不可能实现输出aaa因为低分可能高分不可能挑战成功。否则检查是否存在Sa∈F(a)S_a \in F(a)Sa​∈F(a)和Sb∈F(b)S_b \in F(b)Sb​∈F(b)使得Sa∩Sb∅S_a \cap S_b \emptysetSa​∩Sb​∅。若存在则两人可同时说真话输出bbb否则无论高分如何分解都会与低分的所有分解产生冲突即高分者必然说谎输出aaa。解题思路枚举所有可能的分解由于葡萄编号最大100100100得分可能很大但不超过100!100!100!但输入得分不会太大实际上样例中得分为整数且可能较大但搜索时只需分解到因子不超过100100100。对每个得分使用深度优先搜索DFS\texttt{DFS}DFS生成所有可能的分解方式。搜索时因子按升序选择避免重复组合且每个因子只能使用一次。冲突检测对于低分的每一种分解SaS_aSa​检查是否存在高分的某一种分解SbS_bSb​与SaS_aSa​无交集。若存在则返回真两人可同时说真话。否则返回假。判定流程输入两数aaa和bbb确保aba bab。分别生成aaa和bbb的所有分解。若F(a)F(a)F(a)为空输出bbb。否则若F(b)F(b)F(b)为空输出aaa。否则若存在无冲突的分解组合输出bbb否则输出aaa。复杂度分析得分分解数量有限因为因子必须互异且不超过100100100搜索深度不超过因子个数最多777个因为2×3×5×7×11×13×171002 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 1002×3×5×7×11×13×17100但实际可能更多小因子但最大分解数不会太大。每个得分最多生成几百个分解冲突检测为O(∣F(a)∣⋅∣F(b)∣)O(|F(a)| \cdot |F(b)|)O(∣F(a)∣⋅∣F(b)∣)完全可接受。代码实现// Gizilch// UVa ID: 653// Verdict: Accepted// Submission Date: 2017-06-07// UVa Run Time: 0.010s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structstate{intscore;vectorintgrapes;};boolreferee(vectorvectorintpossible1,vectorvectorintpossible2){for(inti0;ipossible1.size();i){setintused;for(intk0;kpossible1[i].size();k)used.insert(possible1[i][k]);for(intj0;jpossible2.size();j){boolconflictedfalse;for(intk0;kpossible2[j].size();k)if(used.find(possible2[j][k])!used.end()){conflictedtrue;break;}if(!conflicted)returntrue;}}returnfalse;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intscore1,score2;while(cinscore1score2){if(score1score2)swap(score1,score2);vectorvectorintpossible1,possible2;queuestateunvisited;unvisited.push(state{score1,vectorint()});while(!unvisited.empty()){state currentunvisited.front();unvisited.pop();if(current.score1){possible1.push_back(current.grapes);continue;}intstart0;if(current.grapes.size()0)startcurrent.grapes.back();for(intistart1;i100;i)if(current.score%i0){state nextcurrent;next.scorecurrent.score/i;next.grapes.push_back(i);unvisited.push(next);}}unvisited.push(state{score2,vectorint()});while(!unvisited.empty()){state currentunvisited.front();unvisited.pop();if(current.score1){possible2.push_back(current.grapes);continue;}intstart0;if(current.grapes.size()0)startcurrent.grapes.back();for(intistart1;i100;i)if(current.score%i0){state nextcurrent;next.scorecurrent.score/i;next.grapes.push_back(i);unvisited.push(next);}}if(possible1.size()0)coutscore2\n;else{if(possible2.size()0)coutscore1\n;else{if(referee(possible1,possible2))coutscore2\n;elsecoutscore1\n;}}}return0;}总结本题通过枚举所有可能的葡萄组合分解并检查是否存在无冲突的组合从而判断双方是否可能同时说真话进而确定官方胜者。关键点在于正确理解规则优先级并实现高效的分解枚举和冲突检测。由于得分分解数量有限暴力搜索完全可行。该解法清晰直观适合作为组合枚举和集合交集判断的练习。