nyoj——139-我排第几个

川长思鸟来 2022-05-17 22:20 114阅读 0赞

## 我排第几个 ##

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

难度：3

描述

现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？

输入

第一行有一个整数n（0<n<=10000）;  
随后有n行，每行是一个排列；

输出

输出一个整数m，占一行，m表示排列是第几位；

样例输入

3
    abcdefghijkl
    hgebkflacdji
    gfkedhjblcia

样例输出

1
    302715242
    260726926

来源

[\[苗栋栋\]原创][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 f()
    {
        int i,j,k=11;
        for(i=0;i<12;i++)
        {
            int temp=0;
            for(j=i+1;j<12;j++)
            {
                if(s[i]>s[j])
                {
                    temp++;
                }
            }
            ans+=temp*a[k--];
        }
    }
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%s",s);
            ans=0;
            f();
            printf("%lld\n",ans+1);
        }
        return 0;
    }

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