hdu1130&&hdu1023

叁歲伎倆 2023-02-25 15:24 38阅读 0赞

![博客图片][format_png]

## 题目链接 ##

[hdu1130][]

[hdu1023][]

## 题目概述 ##

`hdu1130`让求的是 n n n个结点构成的`BST`的数目. ( 1 ≤ N ≤ 100 ) . (1\\leq N \\leq 100). (1≤N≤100).

`hdu1023`让求的是 n n n个火车进站出站形成的顺序的数目. ( 1 ≤ N ≤ 100 ) . (1\\leq N \\leq 100). (1≤N≤100).

## 解题思路 ##

`hdu1130`求 n n n个结点构成的`BST`的数目,就是求 n n n个结点构成的不同形态的二叉树的数目,也就是 C n C\_n Cn.

`hdu1023`求 n n n个火车进站出站形成的顺序的数目,实际也就是 n n n个元素出栈入栈形成的序列的数目,解决的方法是把入栈看做 \+ 1 +1 \+1,出栈看做 − 1 -1 −1,总共 n n n次入栈操作, n n n次出栈操作,要求对于任意一个前项部分和 ∑ i = 1 k a i ≥ 0 ,   ( 1 ≤ k ≤ 2 n ) \\sum\_\{i=1\}^k\{a\_i\} \\ge 0,\\, (1 \\leq k \\leq 2n) ∑i=1kai≥0,(1≤k≤2n).对应的结果就是第 n n n个 C a t a l a n Catalan Catalan数 C n C\_n Cn.

因为要求到第**100**项,所以要用要用大整数来做,所以选择`java`来做会方便很多.

## 代码实现 ##

import java.math.BigInteger;
    import java.util.Scanner;
    
    class Main {
        
        public static void main(String[] args){
        
            BigInteger[] ans = new BigInteger[105];
            ans[0] = new BigInteger("1");
            for (int i = 1; i <= 100; i++) {
        
                ans[i] = (ans[i - 1].multiply(new BigInteger(""+(4 * i - 2)))).divide(new BigInteger(""+(i+1)));
            }
            int n = 0;
            Scanner in = new Scanner(System.in);
            while (in.hasNextInt()) {
        
                n = in.nextInt();
                System.out.println(ans[n]);
            }
        }
    }

是的,这两个题目提交的代码是同一个O(∩\_∩)O哈哈~.

## 补充 ##

[format_png]: /images/20230209/68c4baf2c7614eb9bcde9b5600d81961.png
[hdu1130]: http://acm.hdu.edu.cn/showproblem.php?pid=1130
[hdu1023]: http://acm.hdu.edu.cn/showproblem.php?pid=1023