hdu 1023 hdu 1131

阅读量：4114 次

发布时间：2019-05-25

本文共 2687 字，大约阅读时间需要 8 分钟。

How Many Trees?

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1105 Accepted Submission(s): 577

Problem Description

A binary search tree is a binary tree with root k such that any node v reachable from its left has label (v) <label (k) and any node w reachable from its right has label (w) > label (k). It is a search structure which can find a node with label x in O(n log n) average time, where n is the size of the tree (number of vertices).

Given a number n, can you tell how many different binary search trees may be constructed with a set of numbers of size n such that each element of the set will be associated to the label of exactly one node in a binary search tree?

Input

The input will contain a number 1 <= i <= 100 per line representing the number of elements of the set.

Output

You have to print a line in the output for each entry with the answer to the previous question.

Sample Input

Sample Output

Train Problem II

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 730 Accepted Submission(s): 430

Problem Description

As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.

Input

The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.

Output

For each test case, you should output how many ways that all the trains can get out of the railway.

Sample Input

Sample Output

12516796      
             
               
        Hint       
       The result will be very large, so you may not process it by 32-bit integers.

#include<iostream>

#include<cstdio>

#include<cstring>

int h[1001][1001];

int Catlan()

{

memset(h,0,sizeof(h));

h[1][0]=1;

h[1][1]=1;

h[2][0]=1;

h[2][1]=2;

for(int i=3;i<=101;i++)

{

int len=h[i-1][0];

for(int j=1;j<=len;j++)

{

h[i][j]+=h[i-1][j]*(4*i-2);

if(h[i][j]>=10)

{

h[i][j+1]+=h[i][j]/10;

h[i][j]%=10;

}

len=h[i][len+1]==0?len:len+1;

while(h[i][len]>=10)

{

h[i][1+len]=h[i][len]/10;

h[i][len]%=10;

len++;

}

int yu=0;

for(int k=len;k>=1;k--)

{

int temp=(h[i][k]+yu*10)/(i+1);

yu=(h[i][k]+yu*10)%(i+1);

h[i][k]=temp;

}

while(!h[i][len])

len--;

h[i][0]=len;

}

int main()

{

int n;

Catlan();

while(~scanf("%d",&n))

{

for(int i=h[n][0];i>=1;i--)

printf("%d",h[n][i]);

printf("\n");

}

return 0;

}

/******两个典型的卡塔兰数模板题（模板到代码都可以一样），火车那个的话以0表示出栈，1表示进栈，就看得出来了，二叉树的话，假设N个节点，根节点必须要有一个，接下来，可以左边0个，右边n-1个或左边1个，右边N-1个

或，，，，左边N-1个，右边0个，也看得出来是卡塔兰万圣节之夜脱单的同学都和女票出去了，还在刷题，，Orz

不过刷题的感觉还是蛮不错的，哈哈，喜欢这种运动+刷题+和朋友在一起+泡图书馆的感觉！！

你可能感兴趣的文章

nginx反代 499 502 bad gateway 和timeout

查看>>

linux虚拟机安装tar.gz版jdk步骤详解

查看>>

python猜拳游戏

查看>>

python实现100以内自然数之和，偶数之和

查看>>

python数字逆序输出及多个print输出在同一行

查看>>

ESP8266 WIFI数传 Pixhaw折腾笔记

去哪儿一面+平安科技二面+hr面+贝贝一面+二面产品面经

查看>>

element ui 弹窗在IE11中关闭时闪现问题修复

查看>>

vue 遍历对象并动态绑定在下拉列表中

查看>>

Vue动态生成el-checkbox点击无法选中的解决方法