P1088 [NOIP 2004 普及组] 火星人与康托展开

变进制数

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

1. 将火星数变成变进制数
2. 将变进制数加上 m
3. 将变进制数变成火星数

实例

我们来看一个实例： 将 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)。
​

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

末位是 1 进制的，进 3 得 (02230)；
次低位是 2 进制的，满 2 进一得 (02310)；
中间位是 3 进制的，满 3 进一得 (03010)；
次位是 4 进制的，3<4，不进位，得 (03010)；
最后将 (03010) 变回火星数。

首位 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。

以上摘自洛谷题解，作者：yummy

流程图解

程序代码

#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;
}