[蓝桥杯 2014 国 A] 排列序数

题目描述

如果用 a b c d 这 $4$ 个字母组成一个串，有 $4!=24$ 种，如果把它们排个序，每个串都对应一个序号：

  abcd  0abdc  1acbd  2acdb  3adbc  4adcb  5bacd  6badc  7bcad  8bcda  9bdac  10bdca  11cabd  12cadb  13cbad  14cbda  15cdab  16cdba  17...

现在有不多于10个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？

输入格式

一行，一个串。

输出格式

一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是 $0$。

样例 #1

样例输入 #1

bdca

样例输出 #1

11

样例 #2

样例输入 #2

cedab

样例输出 #2

70

提示

时限 1 秒, 256M。蓝桥杯 2014 年第五届国赛

所需变量

char arr[30];//用于存储每个字符

int sum = 0;//代表字符的序号

int sumarr = 0;//代表这个字符串字符总数

int i,j;//循环变量

int num[30] = {0};//代表是否存在

int control ;//代表他前面有多少字符

思路：我们观察上面给的案例不难发现，对于每个字符来说，只要看他后面有多少个在他这个字符的前面，如果有x在他的后面，那么我们最后总数就得加上这个数是第多少个数，用总数减去这个数的阶乘乘上x个数！
首先我们要写上阶乘的部分代码如下：

int solution(int a){if(a == 0){return 0;}if(a == 1){return 1;}else{return a*solution(a-1);}
}

对于输入的字符串我们转字符一个一个输入，然后将其存储起来后我们将哪个数存在就将其数组中的数赋值为1，这样方便我们后期统计有多少个数在其后面！
部分代码如下：

while(~scanf("%c",&arr[sumarr])){if(arr[sumarr] == '\\n'){break;}num[arr[sumarr]-97] = 1;sumarr++;
}

然后后面就是对于每个位置上的进行判断，首先是这个数后面还有几位数的阶乘，乘上后面有多少个在他字符前面的数！这样就能得到这个数位上的序号！
部分代码如下：

for(i = 0;i<sumarr;i++){control = 0;for(j = arr[i]-1;j>=97;--j){if(num[j-97] == 1){control++;}}num[arr[i]-97] = 0;sum += control*solution(sumarr-i-1);
}

最后将思路得到的每个部分整合起来得到完整代码，完整代码如下（编译器是dev，语言是C语言）：

#include<iostream>
using namespace std;
int solution(int a){if(a == 0){return 0;}if(a == 1){return 1;}else{return a*solution(a-1);}
}
int main(){char arr[30];int sum = 0,sumarr = 0,i,j,num[30] = {0,},control;while(~scanf("%c",&arr[sumarr])){if(arr[sumarr] == '\\n'){break;}num[arr[sumarr]-97] = 1;sumarr++;}for(i = 0;i<sumarr;i++){control = 0;for(j = arr[i]-1;j>=97;--j){if(num[j-97] == 1){control++;}}num[arr[i]-97] = 0;sum += control*solution(sumarr-i-1);}cout<<sum;return 0;
}