传送门：https://vjudge.net/contest/374932#problem/D
给你一个独特的字典序
要求输入一个字符串，求它的字典序
求它的字典序其实就是求字典序比它小的字符串有多少个，然后加一就是答案。
例如现在给出xyz，对于不同长度的字符串来说。
长度为1的比它小的有a到z为C(26,1)共26个。
长度为2的比它小的有a开头的C(25,1),b开头的C(24,1)...所以是C(25,1)+C(24,1)+...C(1,1)
如果模拟的话随着长度的增加会非常困难，所以我们考虑用数学公式化简
于是乎我们可以用O(n)的时间把长度不同的比给出串小的个数求出来
对于给出串的每一个位置，可选小的字母总数为前一个位置的字母+1到现在该位置的字母，选择数为len-1-i
最后是组合数C(n,m)的初始化我们使用杨辉三角的地推关系，用dp的过程就可以初始化了
还有要注意的小地方是输入的串不是严格升序的话直接结束程序
#include<iostream> #include<string.h> using namespace std; int c[27][27]; char str[15]; void init() { for(int i=0;i<=26;i++){ for(int j=0;j<=i;j++){ if(j==0||i==j) c[i][j]=1; else c[i][j]=c[i-1][j-1]+c[i-1][j]; } } c[0][0]=0; } int main() { init(); while(cin>>str){ int len=strlen(str); for(int i=1;i<len;i++){ if(str[i]<=str[i-1]){ cout<<0<<‘\n‘; return 0; } } int sum=0; for(int i=1;i<len;i++) sum+=c[26][i]; for(int i=0;i<len;i++){ char ch=(i==0)?‘a‘:str[i-1]+1; while(ch<str[i]){ sum+=c[‘z‘-ch][len-1-i]; ch++; } } cout<<++sum<<‘\n‘; } return 0; }
借鉴博客：https://blog.csdn.net/lyy289065406/article/details/6648492
原文：https://www.cnblogs.com/qq2210446939/p/12951652.html