NYOJ 139: 康托展開求排列字典序排名

問題描述

12 個字符 'a'~'l' 全排列按字典序編號（從 1 開始）。給定一個排列，輸出其排名。n ≤ 10000 查詢。

康托展開公式

排名 = 1 + Σ_i=0..11 (未用字符中比 s[i] 小的個數) * (11-i)!。
預計算階乘 fact[0..12]。遍歷字符串，用 vis[26] 標記已用字符，統計當前字符前有多少未用字符。

代碼

#include <bits/stdc++.h>
using namespace std;
long long fact[13];
int main() {
    fact[0] = 1;
    for (int i = 1; i <= 12; ++i) fact[i] = fact[i-1] * i;
    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        long long rank = 1;
        vector used(12, false);
        for (int i = 0; i < 12; ++i) {
            int cur = s[i] - 'a';
            int cnt = 0;
            for (int j = 0; j < cur; ++j) if (!used[j]) ++cnt;
            rank += cnt * fact[11 - i];
            used[cur] = true;
        }
        cout << rank << '\n';
    }
    return 0;
}