《P1246 编码》

题目描述

编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。

字母表中共有 26 个字母 a,b,c,⋯,z，这些特殊的单词长度不超过 6 且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。

例如：

• a→1；
• b→2；
• z→26；
• ab→27；
• ac→28。

你的任务就是对于所给的单词，求出它的编码。

输入格式

仅一行，被编码的单词。

输出格式

仅一行，对应的编码。如果单词不在字母表中，输出 0。

输入输出样例

输入 #1复制

ab

输出 #1复制

27

代码实现：

#include <iostream>
#include <string>
using namespace std;

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

// 检查单词是否按字母升序排列
bool isAscending(const string& s) {
    for (int i = 1; i < s.length(); ++i) {
        if (s[i] <= s[i - 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    string s;
    cin >> s;

    // 检查单词是否符合要求
    if (!isAscending(s)) {
        cout << 0 << endl;
        return 0;
    }

    int total = 0;
    int k = s.length();

    // 计算长度小于当前单词长度的所有单词数量
    for (int length = 1; length < k; ++length) {
        total += combination(26, length);
    }

    // 计算当前长度下，在输入单词之前的单词数量
    for (int i = 0; i < k; ++i) {
        int current_char = s[i] - 'a' + 1;
        int start = (i == 0) ? 1 : s[i - 1] - 'a' + 2;
        for (int j = start; j < current_char; ++j) {
            total += combination(26 - j, k - i - 1);
        }
    }

    // 最后加上当前单词在其起始字母之后的位置
    total++;

    cout << total << endl;

    return 0;
}