核心内容摘要
丹青幻境应用场景：非遗传承人用Z-Image Atelier复原失传水墨技法图谱
题目描述在2084 20842084年政府为了加强对公民的控制并应对长期存在的法律与秩序问题决定采取一项激进措施为每位公民在左手腕植入一个微型计算机。
该计算机存储个人身份信息并包含发射器以便中央计算机追踪和监控人员的位置。
每个计算机的核心部分是一个唯一的身份识别码最多由50 5050个字符组成这些字符来自 26 个小写字母。
任意给定的识别码所使用的字符集是随机选定的。
生产识别码的复杂过程使得制造商更容易生产那些仅对已有字符进行重排的新识别码而不是生成包含不同字母集合的全新识别码。
因此一旦选定一组字母就会先将所有可能的排列使用完毕然后再更换字母集合。
例如假设某个识别码包含3 33个a、2 22个b和1 11个c那么在这些条件下允许的60 6060个识别码中的三个按字典序从上到下依次是abaabc abaabc abaabc题目要求编写程序帮助生成这些识别码的后继下一个字典序的识别码。
程序接收一个长度不超过50 5050的字符串可能包含重复字符输出该字符串对应字符集合的字典序后继如果已经是最后一个则输出No Successor。
输入与输出格式输入输入包含多行每行一个字符串表示一个识别码以单独一行#结束。
输出对于每个输入的识别码输出其后继识别码或No Successor。
样例输入abaabc cbaba #样例输出ababac No Successor解题思路本题的核心任务是求一个给定字符串的字典序下一个排列。
如果当前排列已是该字符集合所能构成的最大字典序排列则输出No Successor。
排列生成算法字符串的“下一个排列”可以用标准的“下一个排列算法”来求解该算法步骤如下从右向左扫描找到第一个满足s[i] s[i 1]的位置i ii。
如果找不到这样的i ii说明整个序列是降序排列的也就是字典序最大没有后继。
从右向左扫描找到第一个满足s[j] s[i]的位置j jj。
交换s[i]和s[j]。
将位置i ii之后的子串反转即变为升序排列。
该算法的时间复杂度为O ( n ) O(n)O(n)其中n nn为字符串长度本题n ≤ 50 n \leq 50n≤50。
使用标准库函数在C \texttt{C}C中algorithm库提供了next_permutation函数可以直接对字符串或容器求出下一个排列。
如果已经是最后一个排列该函数返回false否则返回true并修改容器内容为下一个排列。
本题特殊之处虽然题目描述中提到了字符集合的概念但实际上我们只需要对输入字符串本身求下一个排列即可。
因为next_permutation会自动处理重复字符和字典序逻辑得到的就是该字符集合的下一个识别码。
代码实现// ID Codes// UVa ID: 146// Verdict: Accepted// Submission Date:
// UVa Run Time:
000s//// 版权所有C2016邱秋。
metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){string line;while(getline(cin,line),line!#){if(next_permutation(line.begin(),line.end()))coutlineendl;elsecoutNo Successorendl;}return0;}复杂度分析时间复杂度每次调用next_permutation为O ( n ) O(n)O(n)其中n nn是字符串长度。
空间复杂度O ( n ) O(n)O(n)用于存储字符串。
总结本题是一个典型的“下一个排列”问题适合用来练习排列生成算法或熟悉标准库的使用。
使用C \texttt{C}C的next_permutation可以简洁高效地解决问题无需手动实现排列生成逻辑。
注意特殊情况——当输入字符串已经是最大字典序时输出No Successor。