NYOJ-143第几是谁

野性酷女 2022-05-17 22:23 229阅读 0赞

## 第几是谁？ ##

时间限制：3000 ms  |  内存限制：65535 KB

难度：3

描述

现在有"abcdefghijkl”12个字符，将其按字典序排列，如果给出任意一种排列，我们能说出这个排列在所有的排列中是第几小的。但是现在我们给出它是第几小，需要你求出它所代表的序列.

输入

第一行有一个整数n（0<n<=10000）;  
随后有n行，每行是一个整数m，它代表着序列的第几小；

输出

输出一个序列，占一行，代表着第m小的序列。

样例输入

3
    1
    302715242
    260726926

样例输出

abcdefghijkl
    hgebkflacdji
    gfkedhjblcia

来源

[\[路过这\]原创][Link 1]

上传者

[路过这][Link 2]

思路：毫无疑问，又是跟康托展开有关，本题是康托展开的逆向实现

PS：[康托展开][Link 3]

代码：

#include<map>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<vector>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=1e6+10;
    typedef long long ll;
    char s[20];
    ll ans=0;
    int b[27],c[27];
    ll a[12]= {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800};
    void ff(ll n)
    {
        int i,j,k=11,q=0,temp=0,ans=0;
        while(k>=0)
        {
            ans=n/a[k];
            n%=a[k--];
            int cnt=0;
            for(i=1; i<=12; i++)
            {
                if(b[i]==0)
                {
                    if(cnt==ans)
                    {
                        c[q++]=i;
                        b[i]=1;
                        break;
                    }
                    cnt++;
                }
            }
        }
    }
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            ll n;
            scanf("%lld",&n);
            ans=0;
            int i,j;
            memset(b,0,sizeof(b));
            ff(n-1);
            for(i=0; i<12; i++)
            {
                printf("%c",c[i]+96);
            }
            printf("\n");
        }
        return 0;
    }

[Link 1]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=%5B%E8%B7%AF%E8%BF%87%E8%BF%99%5D%E5%8E%9F%E5%88%9B
[Link 2]: http://acm.nyist.edu.cn/JudgeOnline/profile.php?userid=%E8%B7%AF%E8%BF%87%E8%BF%99
[Link 3]: https://blog.csdn.net/lee371042/article/details/81223744