【CSU-1828】解题报告（数论，康托展开逆展开）

原始题目

1828: Dictionary

  • Time Limit: 2 Sec
  • Memory Limit: 128 Mb
  • Submitted: 202
  • Solved: 146

Description

The isolated people of MacGuffin Island have a unique culture, and one of the most interesting things about them is their language. Their alphabet consists of the first 9 letters of the Roman alphabet (a, b, c, d, e, f, g, h, i). All of their words are exactly 9 letters long and use each of these 9 letters exactly once. They have a word for every possible permutation of these letters. In the library of their most sacred temple is a dictionary, and each word in their language has its own page. By coincidence they order their words exactly as they would be in ordered in English, so the word ‘abcdefghi’ is on the first page, and the word ‘ihgfedcba’ is on the last. The question is, given a list of random words from the MacGuffin language, can you say on which page of the MacGuffin dictionary each appears?

Input

The first line of the input file is a positive integer. This integer tells you how many words will follow. The upper limit for this number is 6000. Every subsequent line contains a single word from the MacGuffin language, so if the first number is 1000 there will be 1000 lines after it, each containing a single word.

Output

Each line of output will contain an integer. This integer should be the page number for the corresponding word.

Sample Input

4
abcdefgih
abcdefghi
abcdefgih
ihgfedcba

Sample Output

2
1
2
362880

Hint

Source

ACM-ICPC Asia Thailand National On-Site Programming Contest 2015

题目大意

输入一个由(a, b, c, d, e, f, g, h, i)各出现一次构成的八位字符串，求其在按字典序排列中的序号。

解题思路

看作1-8的排列，利用康托展开输出序号，模板题。

解题代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define mp make_pair
#define np next_permutation
#define pb push_back
#define all(x) x.begin(),x.end()
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define ms(x,a) memset((x),a,sizeof((x))) 
#define mod 998244353 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int maxl=10;
const int maxn=1e5+5;
int A[maxl];//阶乘； 
int ans_cantor[maxl];//康托展开数组 
bool vis_cantor[maxl];//康托标记数组 

string ss;
void init(){
	A[0]=A[1]=1;
	A[2]=2;
	rep(i,3,maxl+1) A[i]=A[i-1]*i;
}
//contar展开，逆展开，数组标号都是从0开始 
void cantor(int contar_s[], ll num, int contar_k){//康托展开，把一个数字num展开成一个数组contar_s，contar_k是数组长度
    int t;
    memset(vis_cantor, 0, sizeof(vis_cantor)); 
    for(int i = 0; i < contar_k; i ++){
        t = num / A[contar_k-i-1];
        num%=A[contar_k-i-1];
		int cnt_cantor=0;
		rep(j,0,contar_k){	//计算每位的逆序数 
			cout<<"cnt="<<cnt_cantor<<"t="<<t<<"vis="<<vis_cantor[j]<<endl;
			if(vis_cantor[j]) continue;
			if(cnt_cantor==t){
				contar_s[i]=j+1,vis_cantor[j]=1;break;	
			} 
			++cnt_cantor;
			
		}
    }
    rep(i,0,contar_k) cout<<contar_s[i]<<endl; //输出康拖展开的结果 
}
ll inv_cantor(int contar_s[], int contar_k){//康托逆展开，把一个数组contar_s换算成一个数字num 
    int cnt;ll num=0;
    num = 0;
    for(int i = 0; i < contar_k; i ++){
        cnt = 0;
        for(int j = i + 1; j < contar_k; j ++){
            if(contar_s[i] > contar_s[j]) cnt ++;//判断几个数小于它,即求逆序数。 
        }
        num += A[contar_k-i-1] * cnt;
    }
    return num;
} 
int main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	
	init(); 
	while(t--){
		cin>>ss;
		rep(i,0,ss.length()){
			ans_cantor[i]=ss[i]-'a'+1; //这里加不加1都行
		}
		ll num=inv_cantor(ans_cantor,ss.length());
		cout<<num+1<<endl;
	} 
}

收获与反思

  • 感受模板的力量= =