poj 1095 Trees Made to Order
2024-08-31 01:07:56
http://poj.org/problem?id=1095
先求出n个节点数的二叉树的形态有多少种。卡特兰数f[n]=f[n-1]*(4*n-2)/(n+1);再递归求。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define maxn 200
using namespace std; ll f[maxn];
int n,m; void inti()
{
f[]=;
for(int i=; i<; i++)
{
f[i]=f[i-]*(*i-)/(i+);
}
} void deal(int n,int k)
{
int i,sum=;
if(n==) {printf("X"); return ;}
for(i=; sum+f[i]*f[n--i]<k; i++)
{
sum+=(f[i]*f[n--i]);
}
k-=sum;
if(i)
{
printf("(");
deal(i,(k-)/f[n--i]+);
printf(")");
}
printf("X");
if(i!=n-)
{
printf("(");
deal(n--i,(k-)%f[n--i]+);
printf(")");
} } int main()
{
inti();
while(scanf("%d",&n)!=EOF)
{
if(n==) break;
for(int i=; ; i++)
{
if(n>f[i])
{
n-=f[i];
}
else{
m=i;
break;
}
}
deal(m,n);
printf("\n");
}
return ;
}
最新文章
- eclipse:不能在tomcat里添加一个项目的解决方法
- 从C#到Objective-C,循序渐进学习苹果开发(6)--视图控制器的使用
- innodb insert buffer 插入缓冲区的理解
- 使用git命令提交远程github仓库的时候提示";rejected";(拒绝)解决办法
- aix-裸设备文件大小查看
- hdu 1530 最大团模板
- Cloudera Impala 之 ORDER BY without LIMIT currently not supported
- USACO月赛数据
- 算法设计手冊(第2版)读书笔记, Springer - The Algorithm Design Manual, 2ed Steven S.Skiena 2008
- 孙弘与Masa Maso 做互联网最贵的衬衫(2)_人物对话_中国时尚品牌网
- setAttribute设置无效
- 14.Git分支-rebase有趣的例子、变基带来的问题及解决方案
- VS下个人认为比较实用的插件
- js中利用cookie实现记住密码功能
- web api 本地测试
- Expo大作战(五)--expo中app.json 文件的配置信息
- 设计模式入门,策略模式,c++代码实现
- wireMock快速伪造restful服务
- HIVE基本语法以及HIVE分区
- oracle的sign()函数