[NOIP 2006 普及组] Jam 的计数法

知识点

字典序、组合枚举、字符串

解题思路

从右往左找最靠右的位置i，使其字母还能增加且为后续w-1-i个字母留出空间。将该位加1，后面的每位依次取前一位加1，即得到最小合法后继；最多重复5次，找不到位置就停止。

正确性说明

保持更长的前缀会使字典序更小，所以必须优先增加最右可增位置。该位只加1，后缀取最小递增值，所得串是所有更大合法串中最小的一个。反复取后继即按顺序输出且不跳过。

易错点

最大位置随剩余位数变化；不能在末尾字母进位后保留过大的后缀；后续不足5个时不要回绕。

复杂度

时间O(5w)，空间O(w)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int s,t,w;string a;cin>>s>>t>>w>>a;for(int step=0;step<5;step++){int i=w-1;while(i>=0&&a[i]>='a'+t-1-(w-1-i))--i;if(i<0)break;++a[i];for(int j=i+1;j<w;j++)a[j]=a[j-1]+1;cout<<a<<'\n';}}