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.
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
题目大意：
判断一个字符串在字典中的位置。
字符串必须保证为升序字符串才能合法。
解题思路：
组合数学问题。
首先通过dp打印出来com[][]杨辉三角形。
假设字符串的长度为len。
详情见备注。
Code：
/*************************************************************************
> File Name: poj1850.cpp
> Author: Enumz
> Mail: 369372123@qq.com
> Created Time: 2014年10月28日 星期二 01时32分11秒
************************************************************************/ #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<list>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<climits>
#define MAXN 100000
using namespace std;
long long com[][];
void init() /*打印杨辉三角*/
{
for (int i=; i<=; i++)
for (int j=; j<=i; j++)
if (!j||i==j)
com[i][j]=;
else
com[i][j]=com[i-][j-]+com[i-][j];
com[][]=;
}
int main()
{
init();
char num[];
scanf("%s",num);
int len=strlen(num),k;
for (k=;k<=len-;k++) /*判断是否为递增字符串*/
if (num[k]<=num[k-]) break;
if (k!=len)
{
cout<<<<endl;
return ;
}
long long ans=;
/*任意长度小于等于len的数都在其前面*/
for (int i=; i<=len-; i++)
ans+=com[][i];
/*计算最高位为[a,num[0])的个数*/
for (char i='a'; i<num[]; i++)
ans+=com['z'-i][len-];
/*计算前j位相同的个数*/
for (int j=;j<=len-;j++)
/*第j位可能的数字为[num[j-1]+1,num[j]) */
for (char i=num[j-]+;i<num[j];i++)
ans+=com['z'-i][len--j];
cout<<ans+<<endl;
return ;
}
