P1246 编码

admin

https://www.luogu.org/problemnew/show/P1246

题目描述
编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数宇。

字母表中共有26个字母{a，b，…，z}，这些特殊的单词长度不超过6且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。

例如：

a→1 b→2 z→26 ab→27 ac→28

你的任务就是对于所给的单词，求出它的编码。

输入输出格式
输入格式：
仅一行，被编码的单词。

输出格式：
仅一行，对应的编码。如果单词不在字母表中，输出0。

输入输出样例
输入样例#1：
ab
输出样例#1：
27

admin

一流留给自己

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int C(int m1,int n1)
    
14. {
    
15.     double t=1.00;
    
16.     for(int i=0;i<n1;i++)
    
17.         t*=(m1-i),t/=(n1-i);
    
18.     return floor(0.5+t);
    
19. }
    
20. string a;
    
21. long long all=0;
    
22. int main()
    
23. {
    
24.     cin>>a;
    
25.     for(int i=1;i<a.size();i++)
    
26.         all+=C(26,i);
    
27.     for(int i=1;i<a.size();i++)
    
28.         if(a[i-1]>=a[i])
    
29.         {
    
30.             printf("0");
    
31.             return 0;
    
32.         }
    
33.     for(int i=0;i<a.size();i++)
    
34.         for(int j=i!=0?a[i-1]-'a'+1:0;j<=(i==a.size()-1?a[i]-'a':a[i]-'a'-1);j++)
    
35.             all+=C(25-j,a.size()-1-i);
    
36.     printf("%lld",all);
    
37.     return 0;
    
38. }

复制代码

liubo

本题本质上是一个找规律填表的题目

思路非常明确，举一个简单的例子：



------------
对于一个字符串“ade”，它的长度为3.

那么他在题设要求中的字符串编号可以用以下方式求解：

1.  所有**长度为1和2**的字符串数量 + 所有**开头为a**，**由bc到de**的字符串数量；
2.  所有开头为a，由bc到de的字符串数量就相当于所有**开头为d长度为2**的字符串数量加上**开头为d长度为2直到末位是e**的字符串数量；



------------
由以上例子第二条我们可以类比其他情况，得到这样一个表格

**~~P.S.你可以在Excel中很轻松地制作出这个表格~~**

在该表格中，横行表示开头字母，纵行表示字串长度，表格中的数据以该字母开头的该长度字符串的总数

对于任何一群以i开头，长度为j的字符串，它的数量均为可以以这样一个公式表示：

## f[i][j] = f[i + 1][j - 1] + f[i + 2][j-1] + f[i + 3][j - 1] + … + f[z][j - 1]

如果无法理解，没关系，我们再举一个例子



------------
以a开头，长度为3的字符串数量如何计算？

这样的字符串有很多： abc acd ace ...

我们可以发现，这样的字符串的数量就相当于以b开头的长度为2的串的数量，加上以c开头长度为2的串的数量...一直到以y开头长度为2的串的数量，即为以上公式

**（由于题设要求，没有以z开头长度为2的合法串）**


------------

但这样一个公式计算起来仍不方便，别急，我们再来看

由上面的公式，我们可以得到这样一个式子

### f[i + 1][j] = f[i + 2][j - 1] + f[i + 3][j - 1] +…+f[z][j - 1]

在这里，我们用i + 1替换了上题的i，得到了这样一个式子

将这个式子带入刚刚的公式，我们可以得到表格的计算方法：

## f[i][j] = f[i + 1][j - 1] + f[i + 1][j]

用程序运行这个公式，计算数组f[i][j]，就可以得到上述表格

而显然地，计算某个字符串的编号，就是计算字符串每一位在对应行从a到该位的值得和，说的比较抽象，举个例子就能理解



------------
对于一个字符串“ade”：

从右至左，第一位是1，则第一行将a-e的数值相加

第二位是d，将第二行a-d的数值相加

以此类推，得到最终答案399.



------------
至此，本题思路已分析完毕，接下来就是代码实现，需要注意一些细节的处理（数组下标一类），以下是完整代码

```
#include<iostream>
using namespace std;
string s;
int f[30][10],ans,cnt;
int main(){
    cin >> s;
    for(int i = 1;i < s.size();i++){
        if(s[i - 1] >= s[i]){
            cout << 0;
            return 0;
        }
    }
    //判断字符串是否合法（升序）
    for(int i = 1;i <= 26;i++)
        f[i][1] = 1;
    //长度为1的字符串数量都是1
    for(int j = 2;j <= 6;j++)
        for(int i = 27 - j;i > 0;i--)
            f[i][j] = f[i + 1][j - 1] + f[i + 1][j];
    //由公式，我们从上至下从右至左进行计算
    for(int j = s.size() - 1;j >= 0;j--){
        cnt++;
        for(int i = 1;i <= s[j] - 'a' + 1;i++)
            ans += f[i][cnt];
    }
    //由以上的思路计算答案
    cout << ans;
    return 0;
}

```

liubo

liubo 发表于 2018-7-7 11:46
本题本质上是一个找规律填表的题目

思路非常明确，举一个简单的例子：

markdown无法显示，大家可以前往luoguP1246查看我上传的题解

admin

楼上刘同学的题解非常好！大家学习下