POJ-2201-Cartesian Tree(笛卡尔树)

Description

Let us consider a special type of a binary search tree, called a cartesian tree. Recall that a binary search tree is a rooted ordered binary tree, such that for its every node x the following condition is satisfied: each node in its left subtree has the key less then the key of x, and each node in its right subtree has the key greater then the key of x.
That is, if we denote left subtree of the node x by L(x), its right subtree by R(x) and its key by kx then for each node x we have
if y ∈ L(x) then ky if z ∈ R(x) then kz > kx
The binary search tree is called cartesian if its every node x in addition to the main key kx also has an auxiliary key that we will denote by ax, and for these keys the heap condition is satisfied, that is
if y is the parent of x then ay Thus a cartesian tree is a binary rooted ordered tree, such that each of its nodes has a pair of two keys (k, a) and three conditions described are satisfied.
Given a set of pairs, construct a cartesian tree out of them, or detect that it is not possible.

Input

The first line of the input file contains an integer number N -- the number of pairs you should build cartesian tree out of (1 OutputOn the first line of the output file print YES if it is possible to build a cartesian tree out of given pairs or NO if it is not. If the answer is positive, on the following N lines output the tree. Let nodes be numbered from 1 to N corresponding to pairs they contain as they are given in the input file. For each node output three numbers -- its parent, its left child and its right child. If the node has no parent or no corresponding child, output 0 instead.
The input ensure these is only one possible tree.

Sample Input

7 5 4 2 2 3 9 0 5 1 3 6 6 4 11

Sample Output

YES 2 3 6 0 5 1 1 0 7 5 0 0 2 4 0 1 0 0 3 0 0

Source

Northeastern Europe 2002, Northern Subregion

思路:题目中说所有的key值都不一样,因此不会存在NO的情况。直接建树再输出即可。

#include #include using namespace std; struct S{ int id,key,val,parent,l,r; }node[50005]; bool cmp(struct S a,struct S b) { return a.key=0 && node[stk[top]].val>node[i].val) top--; if(top>-1)//如果找到一个不大于自己的节点,就成为该节点的右儿子,还要注意让该节点原来的右儿子变成自己的左儿子(key比其大并且小于其val) { node[i].parent=stk[top]; node[node[stk[top]].r].parent=i; node[i].l=node[stk[top]].r; node[stk[top]].r=i; } else//如果没找到不大于自己的节点,就变成新的根 { node[stk[0]].parent=i; node[i].l=stk[0]; } stk[++top]=i; } } int main() { int n,i; while(~scanf("%d",&n)) { for(i=1;i

点击复制链接 与好友分享!回本站首页

您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:C++ 虚函数的缺省参数问题
下一篇:UVA 10837 - A Research Problem(欧拉函数)
相关文章
图文推荐
POJ-2201-Cartesian Tree(笛卡尔树)
ZOJ 3640 Help Me
POJ-2201-Cartesian Tree(笛卡尔树)
CF 518C(Anya and
POJ-2201-Cartesian Tree(笛卡尔树)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-19 人气:0
本文关键词:
分享到:

相关文章

  • POJ 3321 Apple Tree DFS + 树状数组 2012-06-17

    题意:一棵树树上有N个分叉点,分个分叉点上有一个苹果或者没有苹果,现在想知道以某一个分叉点为根节点的子树有多少苹果。 从题目的叙述中可以知道给出的数据并不是一棵二叉树,所以一开始往并查集的方向做,每次更新都要从当前节点一直更新到根节点。 当这棵树是一条单链的时候,这种做法的耗时就显得有点丧心病狂了。。。。 下面说正解。 此题其实为区间查询题,可是问题在于线段书只能查询一段连续的区间内的值,对于离散的点线段树就丝毫无用武之地了。 下面DFS这个大杀器就要粉墨登场了。 若对点重新用DFS时被访问的先

  • poj 2486 Apple Tree (树形dp) 2013-08-29

    Apple Tree Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6674 Accepted: 2208 Description Wshxzt is a lovely girl. She likes apple very much. One day HX takes her to an apple tree. There are N nodes in the tree. Each node has an amount of

  • poj 2367 Genealogical tree(topsort) 2014-11-23

    Language: Default Genealogical tree Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3063 Accepted: 2072 Special Judge Description The system of Martians' blood relations is confusing enough. Actually, Martians bud when they want and where

  • poj 3321 Apple Tree(树状数组) 2012-04-07

    辉煌北大的月赛题质量真高啊,这种树状数组真难想到。 树状数组的基本用法是区间,单点的应用,起初这个怎么都想不到如何套用到树状数组。 转化方法是 将树上的节点信息查询,转为深度优先中节点顺序(代表结点编号)。进结点与出结点分别代表该结点管辖范围。 题目大意级是说,给你一颗树,最初每个节点上都有一个苹果,有两种操作:修改(即修改某一个节点,修改时这一个节点苹果从有到无,或从无到有)和查询(查询某一个节点他的子树上有多少个苹果)。 由于此题数据比较大(N 也就是DFS搜索的时候做标记的过程,这样新的编

  • POJ 2367 Genealogical tree 拓扑排序 2013-04-01

    Description The system of Martians' blood relations is confusing enough. Actually, Martians bud when they want and where they want. They gather together in different groups, so that a Martian can have one parent as well as ten. Nobody will be surpris

  • POJ 2367 Genealogical tree 拓扑题解 2014-06-11

    一条标准的拓扑题解。 我这里的做法就是: 保存单亲节点作为邻接表的邻接点,这样就很方便可以查找到那些点是没有单亲的节点,那么就可以输出该节点了。 具体实现的方法有很多种的,比如记录每个节点的入度,输出一个节点之后,把这个节点对于其他节点的入度去掉,然后继续查找入度为零的点输出。这个是一般的做法了,效果和我的程序一样的。 有兴趣的也可以参考下我这种做法。 #include #include #include using namespace std; const int MAX_N = 101; i

  • poj - 3321 - Apple Tree 2015-01-12

    题意:一棵苹果树有n个结点,开始时每个结点有一个苹果,这n个结点由m条枝连起来,现执行以下两种操作,C x:如果结点x原来有苹果,则把它摘掉,如果没有,则长出1个苹果。Q x:询问以x为根的树的苹果共几个? ——>>这题转换是关键!要求以x为根的树的苹果共几个,如果能够转换为求一个数组a的[L, R]上的连续和,那就可以用ST或者BIT了。事实证明,确实可以做到这种转换。 例如:原来的树如下:如果询问2,那么共有2、4、5这3个苹果,但2、4、5不是连续的呀??? 得用dfs转换后如

  • POJ 2570 Fiber Network(最短路 二进制处理) 2013-02-12

    题目翻译 一些公司决定搭建一个更快的网络,称为“光纤网”。他们已经在全世界建立了许多站点,这 些站点的作用类似于路由器。不幸的是,这些公司在关于站点之间的接线问题上存在争论,这样“光纤网”项目就被迫终止了,留下的是每个公司自己在某些站点之间铺设的线路。 现在,Internet 服务供应商,当想从站点 A传送数据到站点 B,就感到困惑了,到底哪个公司 能够提供必要的连接。请帮助供应商回答他们的查询,查询所有可以提供从站点 A到站定 B的线 路连接的公司。 输入描述: 输入文件包含多个测试数据。每个

  • HDU4925-Apple Tree 2013-08-11

    题意:n*m网格中种苹果,每个网格要么施肥,要么种一个苹果,每个种苹果的格子,如果它的上下左右有各自有施肥的话,每有一个,苹果数量*2,求怎么种使得苹果数量最多。 思路:交叉种植,即黑白染色法可得到最优解。注意特判当n=m=1时的情况。 #include #include #include #include using namespace std; const int MAXN = 105; int n, m; int g[MAXN][MAXN]; int deal(int x, int y)

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.131 (s). 10 q(s)