UVA 11290 Gangs：卡特蘭數與字典序第 k 小合法括號序列構造

問題本質：括號序列的字典序排名與構造

給定 n, k，構造長度 2n-2 的字串，由 'E'(入棧) 和 'S'(出棧) 組成，滿足任意前綴 E 數 ≥ S 數 (合法括號序列)。序列按特定順序排序：S2 先歸零則 S2 < S1；同步歸零則去除首尾比較；共同前綴則去除前綴比較。求第 k 小序列 (k 從 1 起)。

卡特蘭數與遞推結構

合法序列數為卡特蘭數 C_n。任意合法序列可唯一分解為 E + S1 + S + S2，其中 S1, S2 為合法序列 (可能為空)。長度關係：|S1| = 2i, |S2| = 2(n-1-i)。

字典序遞推與計數陣列預處理

定義 f[i] = 長度 2i 合法序列數 (C_i)。
定義 sf[i][j] = 前綴為 E + (長度 2i 序列) + S 且 S1 長度 ≤ 2j 的序列總數。
遞推：sf[i][0] = f[i-1]*f[0]; sf[i][j] = sf[i][j-1] + f[i-j-1]*f[j]。
則 f[i] = sf[i][i-1]。

遞歸構造第 k 小序列

char* solve(char* buf, int n, int k) { // k 0-based
    if (n == 0) return buf;
    if (n == 1) { *buf++ = 'E'; *buf++ = 'S'; return buf; }
    // 找 S1 長度對應的 i
    int i = upper_bound(sf[n], sf[n]+n, k) - sf[n];
    if (i) k -= sf[n][i-1];
    int q = k / f[i], r = k % f[i];
    *buf++ = 'E';
    buf = solve(buf, n - i - 1, q); // S2
    *buf++ = 'S';
    buf = solve(buf, i, r);         // S1
    return buf;
}

完整程式碼 (C++)

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 20;
int f[MAXN], sf[MAXN][MAXN];

void init() {
    f[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        sf[i][0] = f[i-1] * f[0];
        for (int j = 1; j < i; ++j)
            sf[i][j] = sf[i][j-1] + f[i-j-1] * f[j];
        f[i] = sf[i][i-1];
    }
}

char* solve(char* s, int n, int m) { /* 如上 */ }

int main() {
    init();
    int n, m;
    while (scanf("%d%d", &n, &m) == 2 && n+m) {
        --n; --m; // 轉 0-based
        if (m >= f[n]) { puts("ERROR"); continue; }
        char buf[MAXN*2];
        *solve(buf, n, m) = '\0';
        puts(buf);
    }
    return 0;
}

核心洞察總結

• 卡特蘭數計數 + 字典序分塊定位
• 遞歸分解：E (S2) S (S1) —— 注意 S2 在前，S1 在後
• upper_bound 快速定位 S1 長度區塊
• 商餘分別遞歸構造 S2, S1