题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
int a[30];
int C(int m,int n)
{
int mother=1, son=1, i;
for(i=1; i<=n; i++)//1*2*···*n
mother*=i;
for(i=m; i>m-n; i--)//m*(m-1)*···*(m-n+1)
son*=i;
return son/mother;//分母是小的的阶乘,分子是大减小到大,总数小个
}
int main()
{
int t;
string str;
cin >> t;
while(t--)
{
cin >> str;
int sum = 0;
int len = str.length();
for(int i=0; i<len; i++) a[i] = str[i]-'a'+1;//保存字母在字母表中的序号,a是1,
for(int i=1; i<len; i++) sum += C(26,i);//以任意字母开头,长度小于输入字符序列长度的序列个数,并且正序
for(int tmp=1,i=len; i>0; i--) { //tmp是当前第几个字母,i-1是剩下的字母有多少个
for(int j=tmp; j<a[len-i]; j++) //比如a到b有a,就是1次,这个循环可以让首位之前的字母全部加起来
sum += C(26-j,i-1); //26-j代表剩下几个字母没有用,i-1代表剩下几个字母要枚举
tmp = a[len-i] + 1; //这里是让tmp等于下一个字母的序号,比如i为2时,
}
cout << sum+1 << endl;
}
return 0;
}