版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [POJ 1850] Code" categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• POJ
• 数学
• 计数
• 组合数学 date: 2020-07-29 23:27:26

题目链接

原始题面

Description

Transmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character)

The coding system works like this:

• The words are arranged in the increasing order of their length
• The words with the same length are arranged in lexicographical order (the order from the dictionary)

• We codify these words by their numbering, starting with a, as follows:

  a - 1
  b - 2
  ...
  z - 26
  ab - 27
  ...
  az - 51
  bc - 52
  ...
  vwxyz - 83681
  ...

Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code

Input

The only line contains a word. There are some constraints:

• The word is maximum 10 letters length
• The English alphabet has 26 characters

Output

The output will contain the code of the given word, or 0 if the word can not be codified

Sample Input

bf

Sample Output

55

Source

Romania OI 2002

题意简述

给一个只由小写字母组成的, 长度不超过 10 的字符串, 输出其在所有合法的字符串中的字典序排名

合法的字符串指其中的字符按增序排列, 如 abc, wxz

如果字符串非法 (如 aa, bac) 则输出 0

解题思路

当字符串长度为 1 时, 答案就是其对应字符的 ASCII 码与'a'的差加 1

下面讨论字符串长度大于 1 时的情况

我们注意到, 长度为 $k$ 的所有合法字符串的个数为 $\binom{26}{k}$

所以, 设输入的字符串长度为 $k$, 则我们可以把答案拆分成 长度小于 $k$ 的字符串个数 和 长度等于 $k$ 且字典序小于给定字符串的字符串个数 进行求解

前者即为 $\sum_{i=1}^k\binom{26}{i}$, 后者我们这样去考虑

• 对于左起第一位, 设其对应字符的 ASCII 码与'a'的差为 $m$, 则有 $\binom{26-m-1}{k-1}$ 个字符串的字典序小于以该字符开头的字典序最小的字符串
• 对于其他位, 设其对应字符的 ASCII 码与前一位字符的 ASCII 码的差为 $m$, 则有 $\binom{26-m-1}{k-1}$ 个字符串的字典序小于以该字符和该字符左边构成的子串开头的, 字典序最小的字符串

将上述情况结果加起来就是比给定字符串小的字符串数, 加个 1 就是答案了

代码参考