POJ 1085 Code (组合数学 求字符串对应编码)

题目链接

POJ1850

题目大意

输出某个字符串str在字典中的位置，若不是字典中的字符则输出0。 字典中的单词如下图（单词中每个字母严格递增）：

分析

这是一道组合数学题。对于给定字符串str，首先判断其每个字母是否严格递增。 若是字典中的字符，可以先计算长度比str小的符合字典要求的字符串总数sum1，再计算长度等于str的符合字典要求的字符串总数sum2，sum1+sum2+1即为答案。 对于求sum1：我们可以求出长度为m的符合字典要求的字符总数为 Cm26 ，因为字典中的单词没有字母重复，且排列唯一（严格递增），因此就是一个组合。 对于求sum2:自己写的时候不是写得很清楚，参考了别人博客的代码。思路详见程序注释。

代码

#include <iostream> #include <string> using namespace std; int c[27][27],len; void Make_C()//杨辉三角打表组合数 { for (int i=0;i<=26;i++) for (int j=0;j<=i;j++) if (!j||i==j) c[i][j]=1; else c[i][j]=c[i-1][j-1]+c[i-1][j]; } int Code(string str)//求字符串对应编码 { int sum=0,i; /*计算长度比ch小的字符串总共有多少个*/ for (i=1;i<=len-1;i++) sum+=c[26][i]; /*计算长度等于ch且在ch前面的字符串总共有多少个*/ for (i=0;i<len;i++)//i为str的指针，对每一个位置枚举 允许选择的字符ch { char ch=(!i)?'a':str[i-1]+1;//ch = str[i-1]+1 根据升序规则，当前位置的ch至少要比str前一位置的字符大1 while (ch<=str[i]-1) //ch<=str[i]-1 根据升序规则，当前位置的ch最多只能比 str这个位置实际上的字符 小1 { sum+=c['z'-ch][len-1-i];//'z'-ch：小于等于ch的字符不允许再被选择，所以当前能够选择的字符总数为'z'-ch ch++; //len-1-i：ch位置后面（不包括ch）剩下的位数，就是从'z'-ch选择len-1-i个字符 } } return sum+1; } int main() { string str; int i; bool flag; Make_C(); cin>>str; len=str.length(); flag=true; //判断单词中的每个字符是否严格递增 for (i=0;i<len-1;i++) if (str[i]>=str[i+1]) { flag=false; break; } if (flag) cout<<Code(str)<<endl; else cout<<0<<endl; return 0; }