POJ 1095 Trees Made to Order(카트란 수 + 귀속)

5240 단어
설명 정의 두 갈래 트리의 번호: 1.빈 트리 번호 0 2.하나의 노드만 있는 트리 번호는 1, 3.m+1개의 노드가 있는 나무의 번호는 모든 m개의 노드가 있는 나무의 번호보다 크다.노드 수가 같은 나무에 대해 오른쪽 나무 노드 수가 많은 나무의 번호가 작고 오른쪽 나무 노드 수가 같으면 오른쪽 나무에 귀속된다. 같은 오른쪽 나무 노드가 많은 나무의 번호가 작으면 먼저 번호 n을 주고 이 두 갈래 나무를 출력한다. Input 여러 그룹의 입력을 출력한다. 각 그룹의 용례는 정수 n으로 두 갈래 나무의 번호를 표시하고 n=0으로 입력을 끝내고 Output은 각 그룹의 용례에 대해 출력한다. 이 두 갈래 나무를 출력하고 X로 노드를 표시한다.한 쌍의 괄호마다 한 그루의 나무를 표시하고 (왼쪽 트리) X(오른쪽 트리) 형식으로 이 나무를 출력합니다. 물론 빈 트리라면 Sample Input 1 20 311175320 Sample Output X(X) X(X) X(X(X) X(X)) X((X) X(X) X) X) X) X) X를 출력하지 않습니다. m[1]*num[i-2]+...+num[i-2]*num[1]+num[i-1]*num[0],이것은 카트란 수의 정의 중 하나이기 때문에 우리는 카트란 수를 미리 처리하면 i개 노드가 있는 두 갈래 나무 수량을 얻을 수 있다. (이것은 공식을 바꾸어 ktl[i]=ktl[i-1](4*i-2)/(i+1)로 처리할 수 있다.) 그러면 n마다 이 나무에 몇 개의 노드가 있는지 먼저 제시한 다음에 이 나무의 좌우 자목이 비공인지 판단하여 세 가지 상황으로 나누어 귀속 출력하면 된다. 코드
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
#define maxn 33
ll ktl[maxn];
void init()//  
{
    ktl[0]=1;
    for(int i=1;i<maxn;i++)ktl[i]=ktl[i-1]*(4*i-2)/(i+1);
}
void order(int n,int m)// m n  
{
    if(m==1)// X  
    {
        printf("X");
        return ;
    }
    if(n<=ktl[m-1])//  
    {
        printf("X(");
        order(n,m-1);
        printf(")");
    }
    else if(n>ktl[m]-ktl[m-1])//  
    {
        printf("(");
        order(n-(ktl[m]-ktl[m-1]),m-1);
        printf(")X");
    }
    else//  
    {
        int pos;
        for(int i=m-1;i>=1;i--)//  
            if(n>ktl[i]*ktl[m-1-i])n-=ktl[i]*ktl[m-1-i];
            else{pos=i;break;}
        printf("(");
        order(n/ktl[pos]+(n%ktl[pos]!=0),m-1-pos);//  
        printf(")X(");
        order((n-1)%ktl[pos]+1,pos);//  
        printf(")");
    }
}
int main()
{
    init();
    int n;
    while(~scanf("%d",&n),n)
    {
        for(int i=1;i<maxn;i++)//  
            if(n>ktl[i])n-=ktl[i];
            else{order(n,i);break;}
        printf("
"
); } return 0; }

좋은 웹페이지 즐겨찾기