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

题目描述

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

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

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

输入格式

一行，一个串。

输出格式

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

样例 #1

样例输入 #1

bdca

样例输出 #1

11

样例 #2

样例输入 #2

cedab

样例输出 #2

70

提示

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

2.题解

2.1 全排列 next_permutation

思路

由于友好的 0 < n <= 10范围, 使用时间复杂度为O(n!)的全排列函数是没有问题的!
很简单的思路,全排序遍历即可.

代码

#include<bits/stdc++.h>
using namespace std;
int ans = 0; 
int main() {
	string str;
	cin >> str;
	string temp = str;
	sort(str.begin(), str.end());
	do {
		if(str == temp) break;
		ans++;
	} while(std::next_permutation(str.begin(), str.end()));
	cout << ans;
}

2.2 待补充

思路

代码