POJ 1095 Trees Made to Order 카트란 수 및 재 귀 분할
1747 단어 c
제목 링크http://poj.org/problem?id=1095
debug 에서 알 이 깨 질 때 까지 의 문 제 는 원래 카 틀 랜 드 수 를 잘 알 고 있 었 는데,결국 카 틀 랜 드 수 부분 은 매우 물 러 서 계속 디 버 깅 을 하고 있 었 다.
카 틀 란 수 를 미리 처리 한 후에 현재 몇 개의 노드 로 구 성 된 이 진 트 리 를 내 놓 을 수 있 고 현재 노드 의 모든 정렬 에서 의 순위 도 알 수 있 습 니 다.
그 다음 에 재 귀 를 시작 하고 오른쪽 나무 부터 매 거 를 시작 하여 좌우 나무의 노드 개 수 를 판단 하고 재 귀 를 한다.debug 반나절 의 원인 은 제목 을 읽 지 못 했 기 때 문 입 니 다.정렬 관계 가 잘못 되 었 습 니 다.멘 붕 입 니 다.
영 어 를 잘 못 하 는데,과연 다 칠 수 없 으 니,다음 에 문 제 를 읽 을 때 는 반드시 주의해 야 한다.
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL __int64
using namespace std;
LL c[30]={1};
//
void Init(){
for(int i=1;i<=25;i++){
c[i]=c[i-1]*(4*i-2)/(i+1);
}
}
// k cnt
void slove(int k,int cnt){
// ，
if(k==1){
printf("X");
return;
}
// ，
if(cnt<=c[k-1]){
printf("X");
printf("(");
slove(k-1,cnt);
printf(")");
}
// ，
else if(cnt>c[k]-c[k-1]){
printf("(");
slove(k-1,cnt-(c[k]-c[k-1]));
printf(")");
printf("X");
}
else{
int t=k-1,m;
// ，
for(int i=t;i>=0;i--){
if(c[i]*c[t-i]<cnt)
cnt-=c[i]*c[t-i];
else{
m=i;
break;
}
}
printf("(");
//
slove(t-m,cnt/c[m]+(cnt%c[m]!=0));
printf(")X(");
//
slove(m,(cnt-1)%c[m]+1);
printf(")");
}
}
int main(){
int n,m;
Init();
while(scanf("%d",&n)!=EOF&&n){
for(int i=1;;i++){
if(n>c[i])
n-=c[i];
else{
m=i;
break;
}
}
slove(m,n);
printf("
");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
