[ECNA 1995] 编码

题意

合法单词长度不超过 6，字母严格递增。所有合法单词按长度优先、同长度字典序排列，求给定单词排名；非法输出 0。

思路

长度为 l 的递增单词等价于从 26 个字母中选 l 个，共 C(26,l) 个。先累计所有更短长度。

对当前位，枚举比给定字母小且大于前一字母的候选。若当前位置选 candidate，剩余 r 位必须从它后面的 25-candidate 个字母中选择，贡献 C(25-candidate,r)。逐位累计，最后加一得到当前单词本身。

输入先检查长度和相邻字母严格递增，否则排名为零。

Python 知识

zip(letters,letters[1:]) 枚举所有相邻字母对。
any(left>=right for ...) 简洁判断非法顺序。
math.comb 精确计算组合数。
多个 sum(generator) 直接表达“累计更短长度”和“累计更小前缀”。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：条件检查和组合计数生成器。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：字符编号转换。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16from math import comb


word = input().strip()
letters = [ord(character) - 97 for character in word]

if len(word) > 6 or any(left >= right for left, right in zip(letters, letters[1:])):
    print(0)
else:
    rank = sum(comb(26, length) for length in range(1, len(word)))
    previous = -1
    for position, current in enumerate(letters):
        remaining = len(word) - position - 1
        rank += sum(comb(25 - candidate, remaining) for candidate in range(previous + 1, current))
        previous = current
    print(rank + 1)

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/**
 * P1246 编码
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

unsigned long long C[30][30]; // 组合数

int main() {
    // 组合数 DP
    for (int i = 0; i <= 26; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
    char s[10];
    scanf("%s", s);
    int len = strlen(s);
    // 检查是否严格递增
    for (int i = 1; i < len; ++i)
        if (s[i] <= s[i - 1]) { puts("0"); return 0; }
    // 编码 = 所有更短单词数 + 同长度字典序排名
    unsigned long long rank = 0;
    // 累加长度 < len 的所有合法单词
    for (int l = 1; l < len; ++l) rank += C[26][l];
    // 同长度中，逐位确定
    int prev = 0; // 前一个字母的编号（0-based）
    for (int i = 0; i < len; ++i) {
        int cur = s[i] - 'a' + 1; // 当前字母编号（1-based）
        int remain = len - i - 1;
        // 在 prev+1 到 cur-1 中选 remain 个字母
        for (int c = prev + 1; c < cur; ++c)
            rank += C[26 - c][remain];
        prev = cur;
    }
    printf("%llu\n", rank + 1); // 排名从 1 开始
    return 0;
}

复杂度

单词最长 6，最多枚举 26 个候选，可视为 $O(1)$ 时间和空间。

总结

字典序排名的通用方法是：先数更短对象，再逐位数“当前位置更小”的合法补全数量。

目录

题意

思路

Python 知识

代码

复杂度

总结