hdu 1512 & zoj 2334 Monkey King (왼쪽 나무 + 검색 집합 (최적화 되 지 않 은 소박 함 과 검색 집합)

1691 단어 데이터 구조
한 숲 속 에는 원숭이 N (N < = 10000) 마리 가 살 고 있 었 다.처음에 그들 은 서로 알 지 못 했다.그러나 시간 이 지 날수 록 원숭이 들 은 싸움 이 빠 질 수 없 지만 서로 모 르 는 두 원숭이 사이 에서 만 발생 할 수 있다.싸 울 때 두 원숭이 는 그들 중 가장 강 한 한 마 리 를 불 러 싸움 을 벌 인 다.싸 운 후에 이 두 원숭이 들 은 서로 알 게 되 었 다.  원숭이 마다 강 한 값 이 있 지만 초 대 된 두 마리 의 원숭이 가 싸 우 면 그들의 강 한 값 은 반 으로 줄어든다 (예 를 들 어 10 은 5, 5 는 2 로 줄어든다).현재 각 원숭이 의 초기 강 장 치 를 제시 하고 M 번 의 싸움 을 한다. 싸 우 는 두 원숭이 가 모 르 면 싸움 후 두 원숭이 가 아 는 원숭이 중에서 가장 강 한 원숭이 의 강 장 치 를 출력 한다. 그렇지 않 으 면 수출 - 1.
hdu  http://acm.hdu.edu.cn/showproblem.php?pid=1512
zoj  http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2334
왼쪽 나무 입문 상세 한 내용 은 강 의 를 보십시오. 먼저 강 의 를 보고 왼쪽 나무의 실현 을 이해 하고 링크 를 다운로드 해 야 합 니 다.
http://download.csdn.net/detail/hnust_taoshiqian/8941099 
#include
#include
#include
#include
#include
#define MT(x,i) memset(x,i,sizeof(x))
using namespace std;
const int maxn=100000+10;
int tot,v[maxn],l[maxn],r[maxn],d[maxn],fa[maxn];
///value，left，right，dist(        （  ：        ）)
int Merge(int x,int y){
    if(x==y) return x;
    if(!x) return y;
    if(!y) return x;
    if(v[x]y。   
    r[x]=Merge(r[x],y);
    fa[r[x]]=x;///    
    if(d[l[x]]v[fy]) printf("%d
",v[fx]);
            else printf("%d
",v[fy]);
            Merge(fx,fy);
        }
    }
    return 0;
}
Moderate BST 양 방향 링크 @ CareerCup
BOJ 2642 전개도

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage