【洛谷 P8620】[蓝桥杯 2014 国 A] 排列序数 题解（字符串+排序+全排列）

本文主要是介绍【洛谷 P8620】[蓝桥杯 2014 国 A] 排列序数 题解（字符串+排序+全排列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[蓝桥杯 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 年第五届国赛

---

思路

首先从输入中读取一个字符串 s，并将其拷贝到 ss。然后对 ss 进行排序，得到了 ss 的字典序最小排列。

接下来，进行一个 do-while 循环，每次循环中，都会对 ss 进行一次字典序的下一个排列操作，同时如果 s 和 ss 相等，就跳出循环。每进行一次排列操作，都会使计数器 ans 增加 $1$，这样就可以得到 s 在所有排列中的序号。

最后，输出 ans，即 s 在所有排列中的序号。

---

AC代码

#include <algorithm>
#include <cmath>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;int n;
string s, ss;
ll ans = 0;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> s;ss = s;sort(ss.begin(), ss.end());do {if (s == ss) {break;}ans++;} while (next_permutation(ss.begin(), ss.end()));cout << ans << "\n";return 0;
}

这篇关于【洛谷 P8620】[蓝桥杯 2014 国 A] 排列序数 题解（字符串+排序+全排列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---