题解：P1061 [NOIP2006 普及组] Jam 的计数法

Doraeman · 2025-01-16 21:36:16 · 题解

思路

1. 如果第 n 位的字母是最大序号，应当向前找到第 1 个不相邻的字母，并将其进一位，紧随其后填上每个数。
2. 如果第 n 位的字母不是最大序号，直接向右移动一位。

代码

#include<bits/stdc++.h>
using namespace std;
int a[30], L, R, n; 

//输出函数 
void print(){
    for(int i=1; i<=n; i++)
        cout << (char)(a[i]+'a'-1);
    puts("");
}

// 模拟 
void go(){
    // 如果最后一个字母不是临界点（=R），直接最后一个字母右移1位即可 
    if(a[n] < R){
        a[n]++;
        print();
        return;
    }

    // 最后一个字母是临界点，查找第一个空位 
    for(int i=n; i>1; i--)
        // 找到空位，按照思路操作 
        if(a[i] != a[i-1] + 1){
            // 2 4 6 9 10
            // 2 4 7 8 9
            a[i-1]++;
            for(int j=i; j<=n; j++)
                a[j] = a[i-1] + (j - i) + 1;
            print();
            return;
        }

    // 之所以退出循环，是因为没有找到空位，那么+1也必然找不到，直接结束程序即可 
    exit(0);
}
int main(){
    string s;
    cin >> L >> R >> n >> s;
    for(int i=0; i<n; i++)
        a[i+1] = s[i] - 'a' + 1;

    int T = 5;
    while(T--) go();
}