P1532 卡布列克圆舞曲网页链接P1532 卡布列克圆舞曲题目描述卡布列克是一位数学家他在研究数字时发现任意一个不是用完全相同数字组成的四位数如果对它们的每位数字重新排序组成一个较大的数和一个较小的数然后用较大数减去较小数差不够四位数时补零类推下去最后将变成一个固定的数6174 61746174这就是卡布列克常数例如4321 − 1234 3087 4321-123430874321−12343087。8730 − 378 8352 8730-37883528730−3788352。8532 − 2358 6174 8532-235861748532−23586174。7641 − 1467 6174 7641-146761747641−14676174。如果K KK位数也照此办理它们不是变成一个数而是在几个数字之间形成循环称作卡布列克圆舞曲。例如对于五位数54321 543215432154321 − 12345 41976 54321-123454197654321−1234541976。97641 − 14679 82962 97641-146798296297641−1467982962。98622 − 22689 75933 98622-226897593398622−2268975933。97533 − 33579 63954 97533-335796395497533−3357963954。96543 − 34569 61974 96543-345696197496543−3456961974。97641 − 14679 82962 97641-146798296297641−1467982962。我们把82962 , 75933 , 63954 , 61974 82962,75933,63954,6197482962,75933,63954,61974称作循环节即卡布列克圆舞曲。输入格式若干行每行为一个待求“卡布列克圆舞曲”的起始整数n nn。n 2 31 n2^{31}n231输出格式每行为对应整数的循环节数据之间用空格隔开。输入输出样例 #1输入 #14321 54321输出 #16174 82962 75933 63954 61974解题思路本题是数字黑洞卡布列克常数的模拟与循环检测问题通过对整数反复进行“重排最大数减最小数”的操作记录过程中出现的所有数值一旦遇到重复即定位循环节并输出。1. 问题等价转化卡布列克操作对于整数n nn将其各位数字取出分别按升序和降序排列组成最小数n 1 n_1n1​和最大数n 2 n_2n2​计算n ′ n 2 − n 1 n n_2 - n_1n′n2​−n1​。若结果位数不足原数位数在运算过程中自然由数字前导零的忽略而实现“补零”效果例如3087 30873087排序后最小数视为378 378378最大数8730 87308730。循环节定义从某个起点开始反复执行上述操作最终会进入一个循环。循环节即从第一次出现的某个数开始到再次出现该数之前的所有数构成的序列。目标对于每个输入整数n nn输出其进入的循环节数据之间用空格隔开。2. 算法实现输入与初始化循环读取整数n nn直至 EOF。对于每个n nn清空记录数组a下标ind置 0。将初始值n nn存入a[ind]。迭代操作设置标志flag true进入循环。提取n nn的各位数字存入数组b记录位数cnt。对b[1..cnt]排序。构造最小数n1从b[1]到b[cnt]依次拼成十进制数。构造最大数n2从b[cnt]到b[1]依次拼成十进制数。计算新数n n2 - n1。遍历已记录的数组a检查n nn是否已出现过。若已出现a[i] n则循环节为a[i]到a[ind]的所有元素输出后设置flag false结束循环。否则将n nn追加到a[ind]中继续迭代。输出格式每找到一组循环节按顺序输出数字空格分隔最后换行。3. 复杂度分析时间复杂度每次操作需要O ( d log ⁡ d ) O(d \log d)O(dlogd)排序数字d dd为位数最多10 1010位迭代步数受限于整数范围和循环长度远小于10 5 10^5105级别每轮极快。空间复杂度O ( L ) O(L)O(L)存储过程值L LL为循环前序列长度规模很小。总结通过反复执行“重排相减”操作并将每次结果记录下来借助线性查找检测重复精确提取出卡布列克圆舞曲的循环节。由于操作对象不超过2 31 2^{31}231循环长度有限模拟完全可行。代码简要说明全局变量与数组a[100000]记录操作过程中依次产生的数。ind当前记录数量指针。主循环while(cin n)处理多组数据。初始化ind0将n nn存入a[ind]。flagtrue控制迭代直到发现循环。提取数字位到b排序后用n1升序、n2降序做差。遍历已存数组a若a[i] n则输出从i到ind的所有数置flagfalse。否则将新数继续记录。输出每行结束后输出换行。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll ind;ll a[100000],n;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);while(cinn){ind0;a[ind]n;boolflagtrue;while(flag){ll b[20]{0},n10,n20;ll cnt0;while(n){b[cnt]n%10;n/10;}sort(b1,b1cnt);for(ll i1;icnt;i)n1n1*10b[i];for(ll icnt;i1;i--)n2n2*10b[i];nn2-n1;for(ll i1;flagiind;i)if(a[i]n){flagfalse;for(ll ji;jind;j)couta[j] ;}a[ind]n;}coutendl;}return0;}