首页 > 代码库 > POJ 1850 Code(找规律)

POJ 1850 Code(找规律)

2024-07-14 06:56:00   229人阅读

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Code
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 7913 Accepted: 3709

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
//首先观察规律
1+1.....1 
+  (25+...+1)
+((24+..+1) + (23+..+1)+..+1) 
+
[(24+..+1) + (23+..+1)+..+1)]+[(23+..+1)+..+1)]+...[1]
+....
//所以我维护了一个num[10][27]的数组
for(i=26;i>n;i--)    {        sum+=num[n-1][i];        num[n][i]=sum;    }
num[i]中的所有数字相加  就是 代表 第i层完成之后的编号：
举例：bcd
这说明 前面的a开头的肯定完整了 所以这时候就是需要num[0]+num[1]所有元素的和 +num[2][1](代表三个字符的以a开头的所有数量) =bcd=26+325+300=651  然后加上bcd自己 就是652

这只是第一层上面的字母对于a偏移了  ，如果  第n层对第n-1层偏移的话  如
aef  e对b偏移了 那么这个怎么算了
我们可以忽略a 因为这里a对其不产生影响，唯一的影响是对e的起始的偏移位置的影响 
所以我们可以用num[2][b-‘a‘+数组中起始有值的位置]+num[2][c-‘a‘+数组中起始有值的为位置]+....
/*26 +   (25+...+1)(25*24/2 +24*23/2 +...) +( (24*23/2 +...) +(23*22/2+.....) )*/#include<stdio.h>#include<string.h>__int64 num[10][27];void dfs(__int64 n){    __int64 i;    if(n>10) return ;        __int64 sum=0;    for(i=26;i>n;i--)    {        sum+=num[n-1][i];        num[n][i]=sum;    }    dfs(n+1);}int main(void){    __int64 i,j;    char str[15];    for(i=0;i<27;i++) num[0][i]=1;    dfs(1);    while(scanf("%s",&str[1])!=EOF)    {        __int64 len=strlen(str)-1;        __int64 tol=0;        //除掉不满足情况的        for(i=2;i<=len;i++)        {            if(str[i]<=str[i-1]){ printf("0\n");            return 0;}        }        for(i=0;i<len-1;i++)//先算总层        {            for(j=26;j>=i;j--)            {    tol+=num[i][j];            }        }        str[0]=‘a‘-2;//起始的时候处理一下        for(j=len;j>0;j--){            for(i=0;i<str[len-j+1]-(str[len-j]+1);i++)            {                    tol+=num[j-1][j+i+(str[len-j]+1-‘a‘)];            }        }                        printf("%I64d\n",tol);    }    return 0;}

 ps:woshi1993

POJ 1850 Code(找规律)


联系
我们