题解 P1088 【火星人】

yummy · 2018-10-01 11:37:36 · 题解

简单地逛了逛题解区，发现大部分题解分为两种：

next_permutation
手写 next_permutation

于是，我为了不让题解区太单调，也为了拓宽大家的思维，就经过几分钟的努力，想出了一种与众不同的方法。

Updated on 2022.7.14: 添加 \LaTeX，增加变进制数加法的讲解。

变进制数

我们的目标是把全排列转化成一个变进制数，以方便我们进行加法。
对于第 i 根手指，它有 n-i+1 种选择，根据位值原理，要想让每个数对应一个全排列，就要让这一位数是 n-i+1 进制的。

那么，整个过程分为三步：

将火星数变成变进制数
将变进制数加上 m
将变进制数变成火星数

我们来看一个实例：将 1,4,5,2,3 变成变进制数：

首位 1 是 5 种选择 \{1,2,3,4,5\} 的第 1 种，故变为 0（从0开始）
次位 4 是 4 种选择 \{2,3,4,5\} 的第 3 种，故变为 2
中间位 5 是 3 种选择 \{2,3,5\} 的第 3 种，故变为 2
次低位 2 是 2 种选择 \{2,3\} 的第 1 种，故变为 0
末位 3 是 1 种选择 \{3\} 的第 1 种，故变为 0
最后，排列 1,4,5,2,3 变成了(02200)_{unknown}

接下来给它加上 3 变成 (02203)，并处理进位：

末位是 1 进制的，进 3 得 (02230)。
次低位是 2 进制的，满 2 进一得 (02310)。
中间位是 3 进制的，满 3 进一得 (03010)。
次位是 4 进制的，3<4，不进位，得 (03010)_{unknown}。

最后将 (03010)_{unknown} 变回火星数。

首位 0 表示这位应选择 \{1,2,3,4,5\} 的第 1 种，即 1
次位 3 表示这位应选择 \{2,3,4,5\} 的第 4 种（1 被选过了），即 5
中间位 0 表示这位应选择 \{2,3,4\} 的第 1 种，即 2
次低位 1 表示这位应选择 \{3,4\} 的第 2 种，即 4
末位 0 表示这位应选择 \{3\} 的第 1 种，即 3

所以本题答案为 14523 +3= 15243。

代码 37 行，应该是除 STL 外较短的了。

#include<bits/stdc++.h>
using namespace std;
int a[10005];
bool used[10005]={0};
int m,n;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        int x=a[i];
        for(int j=1;j<=a[i];j++)
            x-=used[j];
        used[a[i]]=1;
        a[i]=x-1;
    }
    a[n]+=m;
    for(int i=n;i>0;i--)
    {
        a[i-1]+=a[i]/(n-i+1);
        a[i]%=n-i+1;
    }
    memset(used,0,sizeof(used));
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=a[i];j++)
            if(used[j])
                a[i]++;
        cout<<a[i]+1<<" ";
        used[a[i]]=1;
    }
    return 0;
}

这篇题解是我较早时候发的，通过评论区我纠正了举个栗子那个部分的小问题。
现在我也通过评论区知道我这方法叫做康托展开。如果你想了解更多，可以看这篇博客.