UVa 725 Division

题目描述给定一个整数NNN2≤N≤792 \le N \le 792≤N≤79要求找出所有由555位数字组成的有序对(abcde,fghij)(abcde, fghij)(abcde,fghij)使得abcde/fghijNabcde / fghij Nabcde/fghijN并且这101010个数字000到999恰好各用一次。允许数字的最高位为000。所有满足条件的数对按分子即第一个数递增顺序输出。若没有解输出相应提示。输入以N0N 0N0结束不同NNN的输出之间用空行分隔。输入格式输入包含多行每行一个整数NNN直到输入000结束。输出格式对于每个NNN若存在解则按分子递增顺序输出所有形如xxxxx / xxxxx N的行若无解则输出There are no solutions for N.。不同NNN的输出之间用一个空行分隔。样例输入61 62 0样例输出There are no solutions for 61. 79546 / 01283 62 94736 / 01528 62题目分析题目要求从数字000到999的全排列中将前五位作为分子后五位作为分母检查分子除以分母是否等于给定的NNN。由于NNN的范围是222到797979且101010个数字全排列总数为10!362880010! 362880010!3628800直接枚举所有排列并检查是完全可行的。预处理所有可能的NNN对应的解然后对每个查询直接输出。解题思路采用全排列枚举法。步骤确定如下步骤1\texttt{1}1. 初始化000到999的字符串0123456789。步骤2\texttt{2}2. 使用next_permutation\texttt{next\_permutation}next_permutation生成该字符串的每个排列。对于每个排列提取前555个字符作为分子后555个字符作为分母分别转换为整数numnumnum和dendenden。步骤3\texttt{3}3. 若numdennum dennumden且num%den0num \% den 0num%den0计算商qnum/denq num / denqnum/den。若qqq在222到797979之间则将该组解存入数组answer[q]\textit{answer}[q]answer[q]中。步骤4\texttt{4}4. 对每个qqq将其解按分子即numnumnum升序排序。由于枚举按字典序产生可能已经有序但为保证正确显式排序。步骤5\texttt{5}5. 对于每个输入NNN若answer[N]\textit{answer}[N]answer[N]为空输出无解信息否则按顺序输出所有解。注意不同测试用例间输出空行。该预处理的时间复杂度为O(10!×10)O(10! \times 10)O(10!×10)空间复杂度为O(10!)O(10!)O(10!)对于所有查询可瞬间响应。代码实现// Division// UVa ID: 725// Verdict: Accepted// Submission Date: 2016-11-29// UVa Run Time: 0.290s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structitem{string numerator,denominator;intnumber1,number2,quotient;booloperator(constitemx)const{if(number2x.number2)returnnumber1x.number1;elsereturnnumber2x.number2;}};intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);vectoritemanswer[100];string n0123456789;do{string numeratorn.substr(0,5),denominatorn.substr(5,5);intnumber1stoi(numerator),number2stoi(denominator);if(number1number2number1%number20){intquotientnumber1/number2;answer[quotient].push_back((item){numerator,denominator,number1,number2,quotient});}}while(next_permutation(n.begin(),n.end()));for(inti2;i79;i)if(answer[i].size()0)sort(answer[i].begin(),answer[i].end());intN,cases0;while(cinN,N0){if(cases0)cout\n;if(answer[N].size()0)coutThere are no solutions for N.\n;else{for(autoa:answer[N])couta.numerator / a.denominator a.quotient\n;}}return0;}总结本题利用全排列枚举所有可能的555位数字组合通过预处理将所有答案按商分类存储从而在查询时直接输出简洁高效。关键点在于允许分子分母出现前导零因此字符串方式处理最为方便。排序保证输出顺序符合题目要求。由于10!10!10!仅约360360360万枚举完全可行且可避免重复计算是解决此类“数字全排列整除”问题的典型方法。