题目分析本题要求我们对给定的正整数进行一种特定的数字变换并记录变换过程中形成的“数字链”直到出现重复的数字为止。变换规则如下将当前数字的各位数字按降序排列得到一个大数bigbigbig。将当前数字的各位数字按升序排列得到一个小数smallsmallsmall。计算差值differencebig−smalldifference big - smalldifferencebig−small。用差值作为新的数字重复上述步骤直到新生成的数字已经在之前的链中出现过为止。需要注意数字允许包含前导零例如123412341234的升序排列是123412341234降序是432143214321而308730873087的升序是03783780378 3780378378降序是873087308730。输入数字小于10910^9109最多有500050005000个数字。每条链的长度定义为链中不同数字的个数。输出格式要求每个数字链的输出后跟一个空行。解题思路1. 问题本质这个问题的本质是模拟一个确定的数字变换过程并检测循环。由于每一步变换的结果完全由当前数字的各位数字决定因此这是一个确定性系统。由于数字范围有限小于10910^9109即最多999位可能的数字状态是有限的因此必然会进入循环。2. 算法设计我们需要对每个输入数字输出原始数字格式要求第一行。使用一个集合set记录已经出现过的数字。循环进行变换将当前数字转换为字符串以便对各位数字进行排序。分别按降序和升序排序得到bigbigbig和smallsmallsmall。计算差值。输出当前步骤的算式。检查差值是否已经在集合中如果已存在说明链结束输出链长度。否则将差值加入集合更新当前数字链长度加111。3. 细节处理3.1 数字与字符串的转换在C中可以使用to_string将整数转换为字符串使用stoi将字符串转换为整数。3.2 排序规则降序排列按字符从大到小排序对应较大的数字。升序排列按字符从小到大排序对应较小的数字。注意升序排列后可能产生前导零例如100100100的升序是0011001 10011但stoi会自动忽略前导零因此无需特殊处理。3.3 链的长度统计题目要求链的长度是链中不同数字的个数。在我们的算法中当新生成的差值已经在集合中出现时我们不将它再次加入集合此时链的长度lengthlengthlength已经记录了集合中元素的个数。3.4 循环终止条件循环在发现新生成的差值已经在集合中时终止。例如444444444的情况原始数字444444444降序444444444升序444444444差值为000。000未出现过继续。下一轮000的降序和升序都是000差值为000此时000已经在集合中终止。这样链的长度为222与示例输出一致。4. 复杂度分析每个数字最多变换100010001000次题目保证。每次变换需要排序数字位数最多999排序复杂度可视为O(9log9)≈O(1)O(9 \log 9) \approx O(1)O(9log9)≈O(1)。集合的插入和查找操作平均O(logL)O(\log L)O(logL)其中LLL是当前链长度L≤1000L \leq 1000L≤1000。总时间复杂度对于每个输入数字O(1000log1000)≈O(104)O(1000 \log 1000) \approx O(10^4)O(1000log1000)≈O(104)对于500050005000个数字完全可行。代码实现// Number Chains// UVa ID: 263// Verdict: Accepted// Submission Date: 2016-05-10// UVa Run Time: 0.380s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 降序比较函数用于将数字的各位从大到小排列boolcmp1(charx,chary){returnxy;}// 升序比较函数用于将数字的各位从小到大排列boolcmp2(charx,chary){returnxy;}intmain(){cin.tie(0);cin.sync_with_stdio(false);intnumber;// 持续读入数字直到遇到 0 为止while(cinnumber,number){// 输出原始数字格式要求第一行coutOriginal number was numberendl;intlength1;// 链的长度初始包含原始数字setintappeared;// 记录已经出现过的数字while(true){// 将当前数字转为字符串以便对各位数字排序string textto_string(number);// 降序排列得到大数sort(text.begin(),text.end(),cmp1);intbigstoi(text);// 升序排列得到小数sort(text.begin(),text.end(),cmp2);intsmallstoi(text);// 计算差值intdifferencebig-small;// 输出当前步骤的算式coutbig - small differenceendl;// 如果差值已经在链中出现过则链结束if(appeared.count(difference)0){coutChain length lengthendl;break;}elseappeared.insert(difference);// 将新差值加入集合numberdifference;// 用差值继续下一轮变换length;// 链长度增加}// 每个数字链输出后跟一个空行coutendl;}return0;}总结本题是一个简单的模拟题核心在于正确实现数字各位的排序与差值计算并利用集合检测循环。代码结构清晰使用set记录历史数字避免了复杂的循环检测逻辑。注意输出格式中的空行要求以及链长度的正确计算方式。通过本题可以熟悉C中字符串与整数的转换、排序函数以及集合的使用。
UVa 263 Number Chains
发布时间：2026/5/22 11:17:50
题目分析本题要求我们对给定的正整数进行一种特定的数字变换并记录变换过程中形成的“数字链”直到出现重复的数字为止。变换规则如下将当前数字的各位数字按降序排列得到一个大数bigbigbig。将当前数字的各位数字按升序排列得到一个小数smallsmallsmall。计算差值differencebig−smalldifference big - smalldifferencebig−small。用差值作为新的数字重复上述步骤直到新生成的数字已经在之前的链中出现过为止。需要注意数字允许包含前导零例如123412341234的升序排列是123412341234降序是432143214321而308730873087的升序是03783780378 3780378378降序是873087308730。输入数字小于10910^9109最多有500050005000个数字。每条链的长度定义为链中不同数字的个数。输出格式要求每个数字链的输出后跟一个空行。解题思路1. 问题本质这个问题的本质是模拟一个确定的数字变换过程并检测循环。由于每一步变换的结果完全由当前数字的各位数字决定因此这是一个确定性系统。由于数字范围有限小于10910^9109即最多999位可能的数字状态是有限的因此必然会进入循环。2. 算法设计我们需要对每个输入数字输出原始数字格式要求第一行。使用一个集合set记录已经出现过的数字。循环进行变换将当前数字转换为字符串以便对各位数字进行排序。分别按降序和升序排序得到bigbigbig和smallsmallsmall。计算差值。输出当前步骤的算式。检查差值是否已经在集合中如果已存在说明链结束输出链长度。否则将差值加入集合更新当前数字链长度加111。3. 细节处理3.1 数字与字符串的转换在C中可以使用to_string将整数转换为字符串使用stoi将字符串转换为整数。3.2 排序规则降序排列按字符从大到小排序对应较大的数字。升序排列按字符从小到大排序对应较小的数字。注意升序排列后可能产生前导零例如100100100的升序是0011001 10011但stoi会自动忽略前导零因此无需特殊处理。3.3 链的长度统计题目要求链的长度是链中不同数字的个数。在我们的算法中当新生成的差值已经在集合中出现时我们不将它再次加入集合此时链的长度lengthlengthlength已经记录了集合中元素的个数。3.4 循环终止条件循环在发现新生成的差值已经在集合中时终止。例如444444444的情况原始数字444444444降序444444444升序444444444差值为000。000未出现过继续。下一轮000的降序和升序都是000差值为000此时000已经在集合中终止。这样链的长度为222与示例输出一致。4. 复杂度分析每个数字最多变换100010001000次题目保证。每次变换需要排序数字位数最多999排序复杂度可视为O(9log9)≈O(1)O(9 \log 9) \approx O(1)O(9log9)≈O(1)。集合的插入和查找操作平均O(logL)O(\log L)O(logL)其中LLL是当前链长度L≤1000L \leq 1000L≤1000。总时间复杂度对于每个输入数字O(1000log1000)≈O(104)O(1000 \log 1000) \approx O(10^4)O(1000log1000)≈O(104)对于500050005000个数字完全可行。代码实现// Number Chains// UVa ID: 263// Verdict: Accepted// Submission Date: 2016-05-10// UVa Run Time: 0.380s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 降序比较函数用于将数字的各位从大到小排列boolcmp1(charx,chary){returnxy;}// 升序比较函数用于将数字的各位从小到大排列boolcmp2(charx,chary){returnxy;}intmain(){cin.tie(0);cin.sync_with_stdio(false);intnumber;// 持续读入数字直到遇到 0 为止while(cinnumber,number){// 输出原始数字格式要求第一行coutOriginal number was numberendl;intlength1;// 链的长度初始包含原始数字setintappeared;// 记录已经出现过的数字while(true){// 将当前数字转为字符串以便对各位数字排序string textto_string(number);// 降序排列得到大数sort(text.begin(),text.end(),cmp1);intbigstoi(text);// 升序排列得到小数sort(text.begin(),text.end(),cmp2);intsmallstoi(text);// 计算差值intdifferencebig-small;// 输出当前步骤的算式coutbig - small differenceendl;// 如果差值已经在链中出现过则链结束if(appeared.count(difference)0){coutChain length lengthendl;break;}elseappeared.insert(difference);// 将新差值加入集合numberdifference;// 用差值继续下一轮变换length;// 链长度增加}// 每个数字链输出后跟一个空行coutendl;}return0;}总结本题是一个简单的模拟题核心在于正确实现数字各位的排序与差值计算并利用集合检测循环。代码结构清晰使用set记录历史数字避免了复杂的循环检测逻辑。注意输出格式中的空行要求以及链长度的正确计算方式。通过本题可以熟悉C中字符串与整数的转换、排序函数以及集合的使用。
)
