首先来首歌曲来放松一下吧！

题目背景：

题目描述

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26个小写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。例如，a,b,ab,bc,xyz等字符串都是升序字符串。现在对字母表A产生的所有长度不超过6的升序字符串按照字典序排列并编码如下。

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

对于任意长度不超过6的升序字符串，迅速计算出它在上述字典中的编码。

算法设计：

对于给定的长度不超过6的升序字符串，计算出它在上述字典中的编码。

输入格式

第一行是一个正整数k，表示接下来共有k行。

接下来的k行中，每行给出一个字符串。

输出格式

输出共有k行，每行对应于一个字符串的编码。

数据范围

1≤n≤100000

输入样例：

1
2
3
2
a
ab

输出样例：

1
2
1
27

题目分析：

题目要求：

输入一个字典序字符串，输出对应的编号，注意没有aa，abccd，后面的一定比前面的大！

解题思路：

先举一个例子：假如输入 cdfg ，要怎么计算了？

先看长度为字符串长度的处理：

  • c开头的一定排在a和b开头的后面，我们可以先算出a打头的长度为4的字符串有多少个，用C(26 - 1, 4 - 1) 表示从25个字符中组合3长度的组合种类！这句话是不是相当于C 325 了，即数学中的排列组合的组合，这样既可保证不重不漏，还可以保证字典序正确！
  • a完了，还有b开头的长度为4的字符串种类，即C(26 - 2, 4 - 1)
  • ab完了，到了c，很明显，c不需要处理
  • 往后移动，到了d的位置，c的下一个就是d，不需要处理
  • 下一个f，会发现f一定在e开头的长度为2的字符串之后，所以需要继续统计,即C(26 - 5 , 4 - 3)
  • 继续发现下一个是g，这也是最后一个，就简单了，不需要用到组合，g一定在a之后，最后直接累加一下a ~ g的编号即可！

再看长度小于字符串长度的处理：

很明显：我们处理完毕了字符串本身长度的排序，还没有处理，在自身长度之下，长度为1 ~ len - 1 的长度，不过这就更加简单了！

长度为1：C(26, 1)

长度为2：C(26, 2)

长度为len - 1：C(26, len - 1);

参考一篇题解：点击这里！

题解：

注意：

for循环处理到长度-1位置即可，最后需要单独处理字符串长度为len时的最后一位与a的差值！

这个是关系式，可以好好看看！

sum += C(26 - 1 - (ch - 'a'), len - i - 1);

注意：while 退出去后：ch还得继续++ ！

最后一位与a的编号差值：

sum += str[len - 1] - ch + 1;

具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <string>
#include <iostream>

using namespace std;
typedef long long LL;

int N;

// 计算组合数
LL C(LL num, LL len)
{
	LL res = 1, t = 1;
	for(int i = 0; i < len; i++) res *= num, num --;
	for(int i = len; i >= 1; i--) t *= i;
	return res / t;
} 

int main()
{
	cin >> N;
	string str;
	while(N--)
	{
		cin >> str;
		
		LL sum = 0;
		int len = str.size();
		char ch = 'a';
		for(int i = 0; i < len - 1; i++)
		{
			sum += C(26, i + 1);// 累计字符串长度为1~len-1序号 
			while(str[i] > ch)	// 累计字符串长度为len时的每一位字符 
			{
				sum += C(26 - 1 - (ch - 'a'), len - i - 1);
				ch ++;
			}
			ch ++;
		}
		// 累计字符串长度为len时最后一位 
		sum += str[len - 1] - ch + 1;
		cout << sum << endl;
	} 
	return 0;
}