[原创]NYOJ 139 我排第几个 [康拓展开]【数学】

2016-11-04 13:22:06 Tabris_ 阅读数：385

博客爬取于2020-06-14 22:42:52
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53033813

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=139

---------------------------------------------.
我排第几个
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？

输入
第一行有一个整数n（0 < n<=10000）;
随后有n行，每行是一个排列；
输出
输出一个整数m，占一行，m表示排列是第几位；
样例输入
3
abcdefghijkl
hgebkflacdji
gfkedhjblcia
样例输出
1
302715242
260726926
----------------------------------------------.

解题思路:
本题就是一道康拓展开的入门练习题目
找到这个字符串在字典序中排在第几就行了

求出展开值+1就是了

康拓展开现见这里<-翻目录

附本题代码
-----------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <cmath>
using namespace std;

# define INF      0x3f3f3f3f
# define pb       push_back
# define abs(a)   ((a)>0?(a):-(a))
# define min(a,b) ((a)>(b)?(a):(b))
# define lalal    puts("*******")

typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 10086;
const int N = 1e7+5;

int prime[700000],kp;
bool Is_or[N];

char s1[30];
bool vis[30];
LL a[30];
LL jiecheng[30];

void init()
{
    jiecheng[0]=1;
    for(int i=1; i<=12; i++)
        jiecheng[i]=jiecheng[i-1]*i;
    return ;
}

LL Cantor_expansion(char s1[])
{
    LL x=0;
    int rk=0;
    for(int i=0; i<12; i++)
    {
        rk=0;
        for(int j=11; j>i; j--)
            if(s1[i]>s1[j])rk++;
        a[i]=rk;
    }

    for(int i=0; i<12; i++)
        x+=a[i]*jiecheng[11-i];
    return x+1;
}

int main()
{
    init();
    int _;
    while(~scanf("%d",&_))
    {
        while(_--)
        {
            scanf("%s",s1);
            printf("%I64d\n",Cantor_expansion(s1));
        }
    }
    return 0;
}

------------------------------------.