當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

HDU——1134 Game of Connections

發布時間：2023/10/18 编程问答 112 如意码农

生活随笔收集整理的這篇文章主要介紹了 HDU——1134 Game of Connections 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

　　　　　　　　Game of Connections

　　　　　　Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
　　　　　　　　Total Submission(s): 4844 Accepted Submission(s): 2811

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 | We have carefully selected several similar problems for you: 1133 1131 2067 1267 2018

題意：

這是一個小而古老的游戲。你應該把數字1，2，3，.，2n-1，2n連續地按順時針順序在地上形成一個圓圈，然后畫出一些直線線段，將它們連接成數對。每一個數字都必須相互聯系。沒有兩個區段被允許相交。這仍然是個簡單的游戲，不是嗎？但是，在你寫下了2n的數字之后，你能告訴我，你可以用多少種不同的方式將數字連接成對？生活更艱難，對吧？

思路：

看題意，這道題是不是圓的劃分？！

對，就是圓的劃分，這樣我們又可以用卡特蘭數來做了。。

代碼：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 110
using namespace std;
int n,len,tmp,sum,b[N],a[N][N];
int read()
{
    ,f=; char ch=getchar();
    ; ch=getchar();}
    +ch-'; ch=getchar();}
    return x*f;
}
int catelan()
{
    len=; a[][]=b[]=;
    ;i<;i++)
    {
        ;j<len;j++)
         a[i][j]=a[i-][j]*(i*-);
        sum=;
        ;j<len;j++)
        {
            tmp=sum+a[i][j];
            a[i][j]=tmp%;
            sum=tmp/;
        }
        while(sum)
        {
            a[i][len++]=sum%;
            sum/=;
        }
        ;j>=;j--)
        {
            tmp=sum*+a[i][j];
            a[i][j]=tmp/(i+);
            sum=tmp%(i+);
        }
        ])
         --len;
        b[i]=len;
    }
}
int main()
{
    catelan();
    )
    {
        n=read();
        ) break;
        ;i>=;i--)
         printf("%d",a[n][i]);
        printf("\n");
    }
    ;
}

總結

以上是生活随笔為你收集整理的HDU——1134 Game of Connections的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：帮老娘导入SF信息
下一篇： hadoop job history s