华师一附中OI组

标题: P1246 编码 [打印本页]
作者: admin    时间: 2018-6-25 21:28
标题: P1246 编码
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    时间: 2018-6-25 21:29
一流留给自己
作者: 吴语林    时间: 2018-6-26 11:07
  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    时间: 2018-7-7 11:46
本题本质上是一个找规律填表的题目

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



------------
对于一个字符串“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    时间: 2018-7-7 11:47
liubo 发表于 2018-7-7 11:46
本题本质上是一个找规律填表的题目

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

markdown无法显示，大家可以前往luoguP1246查看我上传的题解
作者: admin    时间: 2018-7-14 10:16
楼上刘同学的题解非常好！大家学习下



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2