首页 > 代码库 > POJ - 1850 Code
POJ - 1850 Code
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.
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.
? 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
题意:按照题目描述给出的定义:
a->1,b->2……z->26,ab->27……vwxyz->83681.
合法的字符串序列是每一个小写字母比后一个小写字母ASCII码要大,不合法输出0。
思路:首先长度小于len 的话,那么就是计算C[26][{1,2...len-1}],至于等于len 的情况就是讨论str[i-1]+1到str[i]
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 50; char str[maxn]; int C[maxn][maxn]; void init() { C[0][0] = 1; C[1][0] = C[1][1] = 1; for (int i = 2; i < 27; i++) { C[i][i] = C[i][0] = 1; for (int j = 1; j < i; j++) C[i][j] = C[i-1][j] + C[i-1][j-1]; } } int main() { init(); while (scanf("%s", str) != EOF) { int flag = 1; int len = strlen(str); for (int i = 1; i < len; i++) if (str[i] <= str[i-1]) { flag = 0; break; } if (!flag) { printf("0\n"); continue; } int ans = 0; for (int i = len-1; i > 0; i--) ans += C[26][i]; for (int i = 0; i < len; i++) { char ch = (i == 0) ? 'a' : (str[i-1]+1); for (int j = ch; j < str[i]; j++) ans += C['z'-j][len-1-i]; } printf("%d\n", ans+1); } return 0; }
POJ - 1850 Code
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。