[蓝桥杯]2017年模拟赛-排列序数

  • 内容
  • 评论
  • 相关
文章目录
[隐藏]

题目

X星系的某次考古活动发现了史前智能痕迹。
这是一些用来计数的符号,经过分析它的计数规律如下:
(为了表示方便,我们把这些奇怪的符号用a~q代替)

abcdefghijklmnopq 表示0
abcdefghijklmnoqp 表示1
abcdefghijklmnpoq 表示2
abcdefghijklmnpqo 表示3
abcdefghijklmnqop 表示4
abcdefghijklmnqpo 表示5
abcdefghijklmonpq 表示6
abcdefghijklmonqp 表示7
.....

在一处石头上刻的符号是:
bckfqlajhemgiodnp

请你计算出它表示的数字是多少?

请提交该整数,不要填写任何多余的内容,比如说明或注释。

思路

一开始看到这题立马想用next_permutation()暴力求解,可是看了一下位数,这样的解析树太大了,这个思路肯定不行。思索很久没有想法后,求助于搜索引擎。然后知道了全排列还有种叫康托展开白话算法(7) 生成全排列的几种思路(二) 康托展开。可是网上的大多数算法都是自己实现没有充分利用STL的优势,其实用上STL后,代码能够简化很多。

算法实现

#include <bits/stdc++.h>
using namespace std;

//阶乘 
long long fn(int n) {
    long long a = 1;
    for(int i = 1; i <= n; i++) {
        a *= i;
    }
    return a;
}

//子数组的首元素在子数组中的字典序位置 
long long an(string str) {
    char ch = str[0];
    sort(str.begin(), str.end());
    return str.find(ch);
}

int main()
{
    long long sum = 0;
    string s = "bckfqlajhemgiodnp";
    int len = s.length();
    for (int i = 0; i < s.length(); i++) {
        sum += fn(len-i-1) * an(s.substr(i));
    }
    cout << sum;
    return 0;
}
//结果:22952601027516