首页 > ACM题库 > HDU-杭电 > HDU 1023 Train Problem II-高精度-[解题报告] java
2013
11-26

HDU 1023 Train Problem II-高精度-[解题报告] java

Train Problem II

问题描述 :

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.

输入:

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.

输出:

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

样例输入:

1
2
3
10

样例输出:

1
2
5
16796

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

题目:Train Problem II

题意:一种严格上升的进站序列,有多少种不同的出站方式?


思路:卡塔兰数的模型,本题要用到大数

卡塔兰数递推公式:

h(0) = h(1) = 1;

h(n)=h(n-1)*(4*n-2)/(n+1);


代码:

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

        public static void main(String[] argv) throws IOException
        {
              Scanner in = new Scanner(new InputStreamReader(System.in));
              
              BigInteger[] ans = new BigInteger[105];
              
              ans[0] = ans[1] = new BigInteger("1");
              
              BigInteger cheng,chu;
              
              for(int i = 2 ; i < 105 ; i++)
              {
            	  cheng = new BigInteger(Integer.toString(4*i-2));
            	  chu = new BigInteger(Integer.toString(i+1));
            	  
            	  ans[i] = (ans[i-1].multiply(cheng)).divide(chu);
              }
              
             
              while(in.hasNext())
              {
            	  int n = in.nextInt();
            	  
            	  System.out.println(ans[n]);
              }

        }
}


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。