卡特蘭數 HDU2067 HDU4165 HDU1134

題目鏈接：https://vjudge.net/problem/HDU-2067

?

小兔的棋盤

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11800????Accepted Submission(s): 5952

Problem Description

小兔的叔叔從外面旅游回來給她帶來了一個禮物，小兔高興地跑回自己的房間，拆開一看是一個棋盤，小兔有所失望。不過沒過幾天發現了棋盤的好玩之處。從起點(0，0)走到終點(n,n)的最短路徑數是C(2n,n),現在小兔又想如果不穿越對角線(但可接觸對角線上的格點)，這樣的路徑數有多少?小兔想了很長時間都沒想出來，現在想請你幫助小兔解決這個問題，對于你來說應該不難吧!

Input

每次輸入一個數n(1<=n<=35)，當n等于－1時結束輸入。

Output

對于每個輸入數據輸出路徑數，具體格式看Sample。

Sample Input

1 3 12 -1

Sample Output

1 1 2 2 3 10 3 12 416024

Author

Rabbit

Source

RPG專場練習賽

Recommend

lcy

?

?

題解：

1?卡特蘭數的初步學習，卡特蘭數應用 。

2.卡特蘭數計算公式：

?1） h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (n>=1) ， 其中 h[0] = 1；

?2） h(n) = c(2n,n) - c(2n,n+1)(n=0,1,2,...) <==>?h(n) = C(2n,n)/(n+1)

?3） h(n) = h(n-1)*(4*n-2) / (i+1)? ……此條計算公式容易溢出

注意：卡特蘭數的計算很容易溢出。

?

代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 35+10;

LL h[MAXN];

void init()
{
    memset(h, 0, sizeof(h));
    h[0] = 1; h[1] = 1;
    for(int i = 2; i<MAXN; i++)
        for(int j = 0; j<i; j++)
            h[i] += 1LL*h[j]*h[i-j-1];
}

int main()
{
    init();
    int kase = 0, n;
    while(scanf("%d", &n) && n!=-1)
        printf("%d %d %lld\n", ++kase, n, 2LL*h[n]);
}

?

?

?

題目鏈接：?https://vjudge.net/problem/HDU-4165

?

Pills

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1626????Accepted Submission(s): 1139

?

Problem Description

Aunt Lizzie takes half a pill of a certain medicine every day. She starts with a bottle that contains N pills.

On the first day, she removes a random pill, breaks it in two halves, takes one half and puts the other half back into the bottle.

On subsequent days, she removes a random piece (which can be either a whole pill or half a pill) from the bottle. If it is half a pill, she takes it. If it is a whole pill, she takes one half and puts the other half back into the bottle.

In how many ways can she empty the bottle? We represent the sequence of pills removed from the bottle in the course of 2N days as a string, where the i-th character is W if a whole pill was chosen on the i-th day, and H if a half pill was chosen (0 <= i < 2N). How many different valid strings are there that empty the bottle?

Input

The input will contain data for at most 1000 problem instances. For each problem instance there will be one line of input: a positive integer N <= 30, the number of pills initially in the bottle. End of input will be indicated by 0.

Output

For each problem instance, the output will be a single number, displayed at the beginning of a new line. It will be the number of different ways the bottle can be emptied.

Sample Input

6 1 4 2 3 30 0

Sample Output

132 1 14 2 5 3814986502092304

Source

The 2011 Rocky Mountain Regional Contest

?

Recommend

lcy

?

題解：

有n片藥，每天吃半片。當天要么在藥罐中抽到把一片完整的藥片，然后分成兩半，吃一半，最后把另一半放回藥罐中；要么抽到半片藥片直接吃。問：有多少種情況？ 單純的卡特蘭數。

?

代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 30+10;

LL h[MAXN];

void init()
{
    memset(h, 0, sizeof(h));
    h[0] = 1;
    for(int i = 1; i<MAXN; i++)
        for(int j = 0; j<i; j++)
            h[i] += 1LL*h[j]*h[i-j-1];
}

int main()
{
    init();
    int n;
    while(scanf("%d", &n) && n)
        printf("%lld\n", h[n]);
}

?

?

?

題目鏈接：https://vjudge.net/problem/HDU-1134

Game of Connections

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5112????Accepted Submission(s): 2934

Problem Description

This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, ... , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect.

It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right?

Input

Each line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 <= n <= 100.

Output

For each n, print in a single line the number of ways to connect the 2n numbers into pairs.

Sample Input

2 3 -1

?

Sample Output

2 5

?

Source

Asia 2004, Shanghai (Mainland China), Preliminary

Recommend

Eddy

?

?

題意：

1~2*n 順時針排列成一圈， 用n條線段連接n對數，要求線段不能有交叉，問：有多少種連接情況？

?

題解：

可以將此題聯想到出棧問題，這樣就轉化成卡特蘭數了。

?

遞推式一：

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    
    public static void main(String[] args){
        
        BigInteger[] a = new BigInteger[105];
        
        a[0] = BigInteger.ONE;
        for(int i=1; i<=100; i++) {
            a[i] = BigInteger.valueOf(0); 
            for(int j=0;j<i;j++){
                a[i] = a[i].add(a[j].multiply(a[i-j-1]));
            }
        }
            
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n=input.nextInt();
            if(n==-1) break;
            System.out.println(a[n]);
        }
    }
}

?

遞推式二：

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    
    public static void main(String[] args){
        
        BigInteger[] a = new BigInteger[105];
        
        a[0] = BigInteger.ONE;
        for(int i=1; i<=100; i++) {
            a[i] = a[i-1].multiply(BigInteger.valueOf(4*i-2)).divide(BigInteger.valueOf(i+1));
        }
            
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n=input.nextInt();
            if(n==-1) break;
            System.out.println(a[n]);
        }
    }
}

?