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

Wy_x · 2022-10-24 19:41:42 · 题解

题目传送门

更好的阅读体验？

如果你看出来方法了，那这道题就是一道裸的全排序题。

思路：

• 因为数据范围是 1 \leq n \leq 10，可以放心使用时间复杂度为 O(n!) 的全排列函数。题目由小到大编号，应选择 next_permutation。

• ans 应该从 0 开始计数。

• 每进行一次全排列后就判断全排列的结果是否和给出的字符串 S 相同，两种情况：

  1. 如果相同，则退出循环，输出现在 ans 的值。
  2. 否则，ans 加一，同时继续全排列当前结果，直到条件 1 成立。

• 关于 next_permutation：不懂请移步这里，根据需要自学。

代码：

#include<bits/stdc++.h>
using namespace std;
string a;
char c[100];
int ans=0;
// 1 ≤ n ≤ 10
//放心使用时间复杂度 O(n!) 的全排列函数
//不会超时 
int main()
{
    cin>>a;
    int l=a.size();
    for(int i=0;i<l;i++)  c[i]='a'+i;
    //因为 a 的长度 == 字符种类，进行初始化 
    //全排列我习惯字符数组，string 的我不会 
    while(true)
    {
        bool flag=1;
        for(int i=0;i<l;i++)
        {
            //判断两个字符串是否相等
            if(a[i]!=c[i])//不相等
            {
                flag=0;//标记
                break;//退出循环
            }
        }
        if(flag) break;
        //如果没有被标记过,就退出循环输出答案
        ans++;
        //注意 ans 要从 0 开始计数，
        //所以加法操作要在 break 后
        next_permutation(c,c+l);
        //求下一个全排列
    }
    cout<<ans;
    //输出编号
    return 0;
}