P1061 Jam 的计数法【洛谷算法习题】

P1061 Jam 的计数法网页链接P1061 Jam 的计数法题目描述Jam 是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数而是使用小写英文字母计数他觉得这样做会使世界更加丰富多彩。在他的计数法中每个数字的位数都是相同的使用相同个数的字母英文字母按原先的顺序排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为 Jam 数字。在 Jam 数字中每个字母互不相同而且从左到右是严格递增的。每次Jam 还指定使用字母的范围例如从2 ∼ 10 2\sim 102∼10表示只能使用b , c , d , e , f , g , h , i , j {b,c,d,e,f,g,h,i,j}b,c,d,e,f,g,h,i,j这些字母。如果再规定位数为5 55那么紧接在 Jam 数字bdfij \texttt{bdfij}bdfij之后的数字应该是bdghi \texttt{bdghi}bdghi。如果我们用U UU、V VV依次表示 Jam 数字bdfij \texttt{bdfij}bdfij与bdghi \texttt{bdghi}bdghi则U V UVUV且不存在 Jam 数字P PP使U P V UPVUPV。你的任务是对于从文件读入的一个 Jam 数字按顺序输出紧接在后面的5 55个 Jam 数字如果后面没有那么多 Jam 数字那么有几个就输出几个。输入格式共2 22行。第1 11行为3 33个正整数s , t , w s, t, ws,t,w用一个空格隔开。其中s ss为所使用的最小的字母的序号t tt为所使用的最大的字母的序号。w ww为数字的位数这3 33个数满足1 ≤ s t ≤ 26 , 2 ≤ w ≤ t − s 1\le st\le 26,2\le w\le t-s1≤st≤26,2≤w≤t−s第2 22行为具有w ww个小写字母的字符串为一个符合要求的 Jam 数字。所给的数据都是正确的不必验证。输出格式最多为5 55行为紧接在输入的 Jam 数字后面的5 55个 Jam 数字如果后面没有那么多 Jam 数字那么有几个就输出几个。每行只输出一个 Jam 数字是由w ww个小写字母组成的字符串不要有多余的空格。输入输出样例 #1输入 #12 10 5 bdfij输出 #1bdghi bdghj bdgij bdhij befgh说明/提示NOIP 2006 普及组 第三题解题思路本题核心是模拟严格递增组合的下一个序列生成规则求解Jam数字的后续值。Jam数字的本质是从指定字母范围内选取w个严格递增的字母组合生成下一个数字的逻辑与组合数递增完全一致。从字符串末尾向前遍历找到第一个可以增大且不超出范围的字符位置将其加1后后续所有字符依次递增保证严格递增的规则重复该操作最多生成5个合法数字若无法继续生成则直接终止。该方法精准匹配题目规则线性遍历生成序列计算量极小完美适配题目要求。总结核心逻辑将Jam数字转化为严格递增的字母组合模拟组合数的下一个序列生成逻辑。关键操作从后向前查找可更新位置修改后后续字符依次递增保证合法性。效率保障单次生成仅遍历字符串一次最多生成5个结果时间复杂度极低。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N2e310;constll mod1e97;constll INF1e18;intmain(){ll s,t,w;string st;cinstwst;for(ll i1;i5;i){boolf1;for(ll jw-1;j;j--){if(st[j]-a1j-wt){st[j];for(ll kj1;kw;k)st[k]st[k-1]1;coutstendl;f0;break;}}if(f)break;}return0;}