poj1850 Code _Code

知识的领域是无限的,我们的学习也是无限期的。这篇文章主要讲述poj1850 Code相关的知识，希望能为你提供帮助。

Code

【poj1850 Code】Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 10059		Accepted: 4816

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??
大致题意：问你一个字符串是按照某种顺序排列的第几个.
分析：先求出长度小于当前字符串的字符串有多少种，可以利用组合数快速统计,没有位上的限制，只是后一位要比前一位大.如果当前统计位数为len的，那么方案数就是C(26,len).
再来统计长度等于当前字符串的字符串有多少种.因为整个序列是单调上升的，如果第i位我们固定的字符是第j个，那么剩下的len-i位就只能用26-j个字符了，那么方案数就是C(26-j,len-i).每个位置的字符的取值是有一个范围限制的.即它必须大于上一个字符，小于当前给定的字符.
犯的一个错误：我处理字符是把字符-‘a’变成数字来处理的，结果有一处忘了-a.最好的解决方法是不要-a,直接用一个int来存.

#include < cstdio>
#include < cstring>
#include < iostream>
#include < algorithm>

using namespace std;

int c[30][30], len, ans;
char s[15];

int main()

c[0][0] = 1;
for (int i = 1; i < = 26; i++)

c[i][0] = 1;
for (int j = 1; j < = 10; j++)
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];

while (~scanf("%s", s + 1))

ans = 0;
bool can = true;
len = strlen(s + 1);
for (int i = 2; i < = len; i++)
if (s[i] < = s[i - 1])

can = false;
break;

if (!can)

printf("0\\n");
continue;

for (int i = 1; i < len; i++)
ans += c[26][i];
for (int i = 1; i < = len; i++)

int ch = s[i] - a, ch2;
if (i == 1)
ch2 = 0;
else
ch2 = s[i - 1] - a + 1;
if (i == len)
ans += ch - ch2;
else

while (ch2 < ch)

ans += c[26 - ch2 - 1][len - i];
ch2++;

ans++;
printf("%d\\n", ans);

return 0;