题解 - [POJ 1850] Code

发表于 更新于 分类于 ， 本文字数： 641 阅读时长 ≈ 2 分钟

题目链接

原始题面

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

1
bf

Sample Output

1
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 就是答案了

代码参考

Show code

POJ_1850view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <iostream>
#include <string>
using namespace std;
const int N = 26 + 1;
i64 c[N][N] = {{1}, {1, 1}};
int main() {
  for (int i = 2; i < N; ++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];
  }
  string str;
  cin >> str;
  for (string::const_iterator it = str.begin() + 1; it != str.end(); ++it)
    if (*it <= *(it - 1)) {
      cout << 0 << endl;
      return 0;
    }
  if (str.size() == 1) {
    cout << str[0] - 'a' + 1;
    return 0;
  }
  unsigned long long ans = 0;
  for (int i = 1; i < str.size(); ++i) ans += c[26][i];
  for (int j = 'a'; j < str[0]; ++j) ans += c['z' - j][str.size() - 1];
  for (int i = 1; i < str.size(); ++i)
    for (int j = str[i - 1] + 1; j < str[i]; ++j)
      ans += c['z' - j][str.size() - i - 1];
  cout << ans + 1;
}