游戏字典序问题 解题报告

描述：

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

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

输入：

输入为一行，一个长度不超过6的升序字符串。

输出：

输出为一行，为对应字符串的编码。注意末尾要有换行。

输入样例：

a
ac

输出样例：

1
28

解题思路：输入几个字母，先是求出它们全部的排列组合的总数，及它们达到最大的上限，由于它们是升序的，所以可以用无序的排列组合求解，接下来就是要减去多加的一些组合，例如，abc，对于第一个字母，应该是多加了b~z的那些组合，要减去它们，以及一些到最好的字母。

代码如下：

#include<iostream>
#include<cstdio>

usingnamespacestd;

intcnk(intn,intk)
{
inti;
if(k==1)
returnn;
intr=n;
for(i=2;i<=k;i++)
r=r*(n-i+1)/i;//组合排列，因为这些数是有序的，所以可以根据公式得到
returnr;
}
intmain()
{
chars[7];
cin>>s;
intans=0;
intl=strlen(s);
for(inti=1;i<=l;i++)//算出这几位数能够达到最大的排序数
ans+=cnk(26,i);
for(i=0;i<l;i++)//减去算多的那些数
ans-=cnk(26-(s[i]-'a'+1),l-i);
cout<<ans<<endl;
return0;
}