题目描述给定一个非负整数nnn定义其“库存”inventory\texttt{inventory}inventory为如下操作的结果统计nnn的十进制表示中每个数字000到999出现的次数然后按数字从小到大的顺序将每个出现次数和对应的数字依次拼接成一个新的整数。例如555314155531415553141中数字111出现222次333出现111次444出现111次555出现333次因此其库存为211314352113143521131435。若某个数字未出现则不写入库存。注意库存中的每个“计数”可能不止一位如100000000000100000000000100000000000有121212个000库存为120111201112011。一个数称为“自库存数”self-inventorying\texttt{self-inventorying}self-inventorying如果它等于自己的库存。若经过jjj次迭代后首次出现自库存数则称该数“经过jjj步后自库存”。若迭代序列进入一个长度k≥2k \ge 2k≥2的循环则称该数“进入长度为kkk的库存循环”。若经过151515次迭代后仍未出现上述三种情况则判定为“无法在151515次迭代内分类”。本题要求对每个输入的非负整数最多808080位进行判断输出相应的分类信息。输入格式输入包含若干个非负整数每行一个每个整数最多808080位没有前导零。输入以一行-1结束。输出格式对于每个输入整数nnn输出以下五种消息之一n is self-inventoryingn is self-inventorying after j stepsn enters an inventory loop of length kn is self-inventorying after 15 steps若第151515次迭代后恰好为自库存数n can not be classified after 15 iterations其中jjj和kkk为相应的正整数。样例输入22 31123314 314213241519 21221314 111222234459 -1输出22 is self-inventorying 31123314 is self-inventorying 314213241519 enters an inventory loop of length 2 21221314 is self-inventorying after 2 steps 111222234459 enters an inventory loop of length 2题目分析本题的核心是模拟库存迭代过程并检测序列中出现的固定点或循环。由于每次迭代后的数字长度不会超过原数字长度的两倍因为每个出现数字对应一个计数计数最多为原长度拼接后长度约为2×102 \times 102×10对于808080位的输入迭代结果长度最多160160160位但实际更小状态空间有限迭代151515次足以判断循环或自库存。参考代码中循环检测使用mapstring,int\texttt{mapstring,int}mapstring,int记录每个字符串首次出现的步骤编号一旦某个字符串重复出现即可根据重复出现的位置判断是自库存、经过若干步自库存还是进入长度大于111的循环。需要特别注意两种边界情况若重复出现的字符串就是起始字符串start 0且循环长度为111则为自库存数。若重复出现的字符串不是起始串start 0且循环长度为111则说明从第start步开始进入自库存数应输出“经过start步后自库存”。若循环长度1 11则输出进入循环。若迭代151515次后未出现重复还需检查第151515次迭代后的字符串是否为自库存数即与下一步相同否则输出无法分类。解题思路实现库存函数getNext(string number)使用mapchar, int统计number中每个字符数字的出现次数。遍历map按键自动升序对于每个键值对(digit, count)先将count转为字符串再追加digit字符拼接得到下一个字符串。主循环处理每个输入读入一个字符串number可能较大用string存储。用mapstring, int cache记录每个出现的字符串及其首次出现的步骤编号从000开始。循环iii从111到151515计算next getNext(number)。若next已在cache中则根据start cache[next]和loop i - start判断若loop 1输出进入长度loop的循环。若start 0输出自库存数。否则输出经过start步后自库存。标记为已确定跳出循环。否则将next记录为第i步出现并将number更新为next。若循环结束时仍未确定计算next getNext(number)即第161616次迭代。若number next则输出“经过151515步后自库存”。否则输出“无法在151515次迭代内分类”。输出格式按题目要求精确输出消息注意空格和标点。复杂度分析每次库存操作需遍历字符串并统计字符出现次数时间复杂度O(L)O(L)O(L)其中LLL为当前字符串长度最多约160160160。迭代次数固定为151515因此每个输入的处理时间为常数。空间复杂度O(15×L)O(15 \times L)O(15×L)用于存储历史字符串。代码实现// Numbers That Count// UVa ID: 613// Verdict: Accepted// Submission Date: 2016-08-31// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;stringgetNext(stringnumber){mapchar,intdigits;for(intj0;jnumber.length();j)digits[number[j]];string next;for(autodigit:digits){nextto_string(digit.second);nextdigit.first;}returnnext;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string number;while(cinnumber,number!-1){coutnumber ;booldeterminatedfalse;mapstring,intcache{{number,0}};for(inti1;i15;i){string nextgetNext(number);if(cache.find(next)cache.end())cache[next]i;else{determinatedtrue;intstartcache[next],loopi-cache[next];if(loop1)coutenters an inventory loop of length loop\n;elseif(start0)coutis self-inventorying\n;elsecoutis self-inventorying after start steps\n;break;}numbernext;}if(!determinated){string nextgetNext(number);if(numbernext)coutis self-inventorying after 15 steps\n;elsecoutcan not be classified after 15 iterations\n;}}return0;}总结本题模拟了简单的迭代过程并通过记录历史状态来检测循环。关键点在于库存操作的准确实现注意多位计数的处理。循环检测时区分循环长度111和长度111以及首次出现位置。处理恰好151515步后自库存的边界情况。使用map\texttt{map}map实现字符串到步数的映射简洁高效。该解法思路清晰代码量小适用于数字长度较大但迭代次数有限的场景。