POJ 1850 Code/POJ 1496 Word Index（组合数学-字母串序号）

布满荆棘的人生 2022-07-10 04:30 79阅读 0赞

Code

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;30000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;9645</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;4617</td> 
  </tr> 
 </tbody> 
</table>

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

Sample Output

Source

[Romania OI 2002][]

## 题目意思： ##

有一个使用26个小写字母a~z的编码系统的工作原理如下：  
•单词按其长度的递增顺序排列。  
•具有相同长度的词按词典顺序排列（来自字典的顺序）。  
•我们通过编号将这些词编码，从a开始，如下：  
a-1  
b-2  
... ...  
z-26  
ab-27  
... ...  
az-51  
bc-52  
... ...  
vwxyz - 83681  
... ...  
  
如果可以根据该编码系统编码，则输出给定字及其代码，否则输出0。

## 解题思路： ##

规律是：n位字符串的所有情况是C(26,n)。

对于给出的n位字符串，先利用规律求出其n-1位的编码，然后遍历字符串每一位累加计算编码。

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXN 30
    int vis[MAXN][MAXN];//用于记忆化搜索，vis[i][j]表示组合数C(i,j)的值
    string s;//输入串
    int len;//串的长度
    int c(int x,int y)//计算组合数C(x,y)
    {
        int s=1,i,j;
        for (i=y+1, j=1; i<=x; i++,j++)
            s=s*i/j;
        return s;
    }
    void solve()
    {
        memset(vis,-1,sizeof(vis));
        int ans=0;
        for(int i=1; i<=len-1; ++i)//计算len-1位的大小
        {
            if(vis[26][i]!=-1)//已经计算过
                ans+=vis[26][i];
            else//未计算
            {
                vis[26][i]=c(26,i);
                ans+=vis[26][i];
            }
        }
        for(int i=0; i<len; ++i)//计算len位中当前串的大小
        {
            char t;
            if(i==0) t='a';//首字符从a开始计算
            else t=s[i-1]+1;//后面的字符从前一个字符的后一位开始计算
            while(t<s[i])//一直计算到当前字符
            {
                if(vis['z'-t][len-1-i]!=-1)
                    ans+=vis['z'-t][len-1-i];
                else
                {
                    vis['z'-t][len-1-i]=c('z'-t,len-1-i);
                    ans+=vis['z'-t][len-1-i];
                }
                ++t;//后一个字母
            }
        }
        cout<<++ans<<endl;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        while(cin>>s)
        {
            bool flag=false;//是否升序
            len=s.size();
            for(int i=1; i<len; ++i)
                if(s[i-1]>s[i])
                {
                    flag=true;//存在降序
                    break;
                }
            if(flag) cout<<"0"<<endl;//字符串非法
            else solve();//字符串合法
        }
        return 0;
    }

[Romania OI 2002]: http://poj.org/searchproblem?field=source&key=Romania+OI+2002