题目链接：uva 11290 - Gangs

题目大意：给出n和k，表示要构造一个长度为2*n-2的字符串，OG序列为k的字符串（类似于出栈入栈）。

• 如果字符s2先回到原点（即栈空），那么s2 OG s1
• 如果s1和s2同事回答原点，那么忽略头尾的ES进行比较
• 如果s1和s2的前t个相同，扣掉前t个字符考虑

  解题思路：出栈入栈的个数是卡特兰数，每次考虑两个部分
  Sstr1Estr2.

  #include 
       
         #include 
        
          #include 
         
           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]; } /* for (int i = 0; i < maxn; i++) printf("%d\n", f[i]); */ } char* solve (char* s, int n, int m) { if (n == 0) return s; if (n == 1) { *s++ = 'E'; *s++ = 'S'; return s; } int k = upper_bound(sf[n], sf[n]+n, m) - sf[n]; if (k) m -= sf[n][k-1]; int q = m / f[k], r = m % f[k]; *s++ = 'E'; s = solve(s, n - k - 1, q); *s++ = 'S'; s = solve(s, k, r); return s; } int main () { init(); int n, m; while (scanf("%d%d", &n, &m) == 2 && n + m) { n--; m--; if (m >= f[n]) printf("ERROR\n"); else { char s[maxn*2]; *solve(s, n, m) = '\0'; printf("%s\n", s); } } return 0; }