算法思路

问题分析

给定单词需满足字母严格递增（即每个字符$<$下一个字符），若合法则计算其编码。编码规则为：所有长度更小的合法单词数 + 同长度且字典序更靠前的单词数 + $1$。

#include <iostream>
#include <string>
#include <vector>

// 计算组合数 C(n, k)
int combination(int n, int k) {
    if (k == 0 || k == n) return 1;
    int result = 1;
    for (int i = 1; i <= k; ++i) {
        result = result * (n - i + 1) / i;
    }
    return result;
}

// 计算单词编码
int encodeWord(const std::string& word) {
    int len = word.length();
    // 检查单词是否按字典序递增
    for (int i = 1; i < len; ++i) {
        if (word[i] <= word[i - 1]) {
            return 0;
        }
    }

    int code = 0;
    // 先加上长度小于当前单词长度的所有单词的数量
    for (int i = 1; i < len; ++i) {
        code += combination(26, i);
    }

    // 计算长度相同但字典序在当前单词之前的单词数量
    for (int i = 0; i < len; ++i) {
        int start = (i == 0) ? 'a' : word[i - 1] + 1;
        int end = word[i];
        for (char c = start; c < end; ++c) {
            code += combination('z' - c, len - i - 1);
        }
    }

    // 加上当前单词在其长度的单词中的序号
    code++;

    return code;
}

int main() {
    std::string word;
    std::cin >> word;

    int code = encodeWord(word);
    std::cout << code << std::endl;

    return 0;
}