题目链接: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];
}
}
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;
}
分享到:
相关推荐
帮派|
目录CSV输出gnuplot输出Excel电子表格输出 执照奥本大学(Auburn University)版权所有2015。 版权所有。 如果满足以下条件,则允许以源代码和二进制形式进行重新分发和使用,无论是否经过修改,都可以: 重新分发源...
以下的资源也很不错, 加减可以看一下o 使用C++制作戰車射擊-100%提供源码 ... 使用C++制作3D动画人物-100%提供源码 ... Linux kernel 每一行都完全注释-初学者必备 ...Programming Embedded Systems 2nd ...
帮派 ###A 插件关于帮派和战斗。 由 Quartz-Dev 团队提供
https://www.journaldev.com/31902/gangs-of-four-gof-design-patterns https://designpatternsphp.readthedocs.io/en/latest/README.html https://refactoring.guru/design-patterns/catalog
1. The spread of gangs and drugs has also been implicated in the increasing violence of school youths. 2. The use of drugs in general population has become a very serious problem in society and within...
它的原意是Gangs Of Four,就是“四人帮”,就是指此书的四个作者:Erich Gamma,Richard Helm,Ralph Johnson,John Vlissides。这本书讲了23种主要的模式,包括:抽象工厂、适配器、外观模式等。??还有其他的很多模式...