Jam的计数法

题目描述

Jam 用小写英文字母计数。一个 Jam 数字是 $w$ 个互不相同、从左到右严格递增的小写字母组成的串，字母只能取序号区间 $[s, t]$ 内的字母（ $1 \leqslant s < t \leqslant 26$ ， $w \leqslant 10$ ，输入保证合法）。所有 Jam 数字按字典序从小到大排列。输入：第 1 行三个整数 $s\ t\ w$ ；第 2 行一个 Jam 数字。输出：紧接其后的至多 $5$ 个 Jam 数字，每行一个；不足 $5$ 个时有几个输出几个。

输入样例：第 1 行 2 10 5，第 2 行 bdfij。

输出样例：bdghi、bdghj、bdgij、bdhij、befgh。

思路

Jam 数字全体就是「从 $[s,t]$ 里选 $w$ 个字母的升序组合」按字典序的排列，求后继等同于“组合加一”：从右往左找第一个未到上界的位（最右位上界是第 $t$ 号字母，其余位上界是右邻位的前一个字母），该位加 1，右边各位重置为紧随其后的最小连续字母。全部顶界说明已是最大数字，停止输出；最多求 5 次，单次 $O(w)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def next_jam(word: str, t: int) -> str | None:
    """求紧接在 word 之后的 Jam 数字；已是最大则返回 None。

    从最右位往左找第一个还能增大的位置：该位的上界是
    t（最右位）或右邻位的前一个字母（其余位，保证严格递增）。
    该位加 1 后，右边所有位取「能取的最小字母」，即紧随其后的连续字母。
    """
    for i in reversed(range(len(word))):
        # 上界：最右位是第 t 号字母，其余位是右邻位的前一个字母（保证严格递增）
        limit = ord('a') + t - 1 if i == len(word) - 1 else ord(word[i + 1]) - 1
        if ord(word[i]) < limit:
            # 右侧 w-1-i 位取 word[i]+1 起的连续字母
            return word[:i] + ''.join(chr(ord(word[i]) + 1 + k)
                                      for k in range(len(word) - i))
    return None


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    s = int(next(tokens))
    t = int(next(tokens))
    w = int(next(tokens))
    word = next(tokens).decode()  # s 在找后继时用不到，读入只为完整解析输入

    out = []
    for _ in range(5):
        word = next_jam(word, t)
        if word is None:
            break
        out.append(word)
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:42
 * update_at: 2026-10-06 13:42
 */

// Jam 数字 = 从区间 [s,t] 里选 w 个字母组成的严格递增序列，
// 全体 Jam 数字按字典序排列。求后继就是"组合加一"：
// 从右往左找第一个未到上界的位，该位加 1，右边各位重置为最小连续字母。
#include <cstdio>
#include <iostream>
#include <string>
typedef long long ll;

const int MAXW = 30;

ll s, t, w;          // s 在求后继时用不到，读入只为完整解析输入
char cur[MAXW];      // cur[i] 表示 Jam 数字第 i 位（从 0 数起）的字母

// 求紧接在 cur 之后的 Jam 数字；已是最大数字则返回 0，否则返回 1
bool next_jam() {
    // 从最右往左找第一个还能加 1 的位
    for (ll i = w - 1; i >= 0; i--) {
        // 上界：最右位是第 t 号字母，其余位是右邻位的前一个字母（保证严格递增）
        char limit = (i == w - 1) ? char('a' + t - 1) : char(cur[i + 1] - 1);
        if (cur[i] < limit) {
            cur[i]++; // 该位加 1
            // 右边各位取紧随其后的最小连续字母，保证严格递增
            for (ll j = i + 1; j < w; j++) cur[j] = char(cur[j - 1] + 1);
            return true;
        }
    }
    return false; // 所有位都顶到上界，说明已是最大 Jam 数字
}

int main() {
    std::cin >> s >> t >> w >> cur;
    for (int k = 1; k <= 5; k++) {
        if (!next_jam()) break; // 后面没有更多 Jam 数字了
        std::cout << cur << "\n";
    }
    return 0;
}

目录

题目描述

思路

参考代码