3066: 【普及/提高-】【P1246】编码
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。
字母表中共有26个字母{a，b，…，z}，这些特殊的单词长度不超过6且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。
例如：
a→1
b→2
z→26
ab→27
ac→28
你的任务就是对于所给的单词，求出它的编码。
输入
仅一行，被编码的单词。
输出
仅一行，对应的编码。如果单词不在字母表中，输出0。
样例输入 复制
ab样例输出 复制
27提示
#include<bits/stdc++.h>
using namespace std;
long long C[30][30];
string str;
int ans;
int main(){
for(int i=0;i<=26;i++) {
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1]); //递推
}
cin >> str;
int len = str.size();
for (int i = 0; i < len; i++)
if (str[i] <= str[i - 1]) { //非升序就是不正确的编码
cout << 0;
return 0;
}
//1、计算出位数比它小的单词数
//比如是cgx,那么就计算出
//1位的有C[26][1]个,2位的有C[26][2]个
for (int i = 1; i < len; i++)ans += C[26][i];
//2、到这就是位数和它自己一样的了。枚举每一位,从低到高，一个个来
for (int pos = 0; pos < len; pos++) {
//每一位都要找到比当前输入字符串小的字符串个数，叠加在一起就是结果
char start = 'a'; //初值为`a`,首位的话，从`a`开始，其它的从上一位的后面一个开始
if (pos > 0) start = str[pos - 1] + 1; //str的数组下标是从0开始的
for (char j = start; j < str[pos]; j++) //注意范围,找比它小的
ans += C['z' - j][len - pos - 1]; //'z' - j 剩下可用的字符数量, len-pos-1需要选择的字符数量
}
cout << ++ans; //别忘了最后把自己加上
return 0;
}