首页 > 代码库 > uva 11290 - Gangs(卡特兰数)
uva 11290 - Gangs(卡特兰数)
题目链接:uva 11290 - Gangs
题目大意:给出n和k,表示要构造一个长度为2*n-2的字符串,OG序列为k的字符串(类似于出栈入栈)。
- 如果字符s2先回到原点(即栈空),那么s2 OG s1
- 如果s1和s2同事回答原点,那么忽略头尾的ES进行比较
- 如果s1和s2的前t个相同,扣掉前t个字符考虑
解题思路:出栈入栈的个数是卡特兰数,每次考虑两个部分
Sstr1Estr2.
#include <cstdio>
#include <cstring>
#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];
}
/*
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;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。