本帖最后由 tiger 于 2023-3-27 19:03 编辑
3506 题目描述 As we know,the shape of a binary searchtree is greatly related to the order of keys we insert. To be precisely:
1. insert a key k to a empty tree,then the tree become a tree withonly one node;
2. insert a key k to a nonemptytree, if k is less than the root ,insert it to the left sub-tree;elseinsert k to the right sub-tree.
We call the order of keys we insert “the order of atree”,your task is,given a order of a tree, find theorder of a tree with the least lexicographic order that generate the sametree.Two trees are the same if and only if they have the same shape. 580/2000 众所周知，二叉查找树的形状与我们插入键的顺序密切相关。准确地说: 1。在一个空树中插入一个键 k，然后该树变成一个只有一个节点的树;。向非空树插入一个键 k，如果 k 小于根，则将其插入到左侧子树; 否则将 k 插入到右侧子树。我们称之为键的顺序，我们插入“树的顺序”，你的任务是，给定一个树的顺序，找到一个树的顺序与最少的字典顺序生成相同的树。两棵树是相同的当且仅当它们具有相同的形状。 输入 There are multiple test cases in an inputfile. The first line of each testcase is an integer n(n <=100,000),represent the number of nodes.The second line has n intergers,k1 tokn,represent the order of a tree.To make if more simple, k1 to kn is a sequenceof 1 to n. 一个输入文件中有多个测试用例。每个测试用例的第一行是一个整数 n (n <= 100,000) ，表示节点的数量。第二行有 n 个整数，k1到 kn，表示树的顺序。为了更简单，k1到kn 是1到 n 的序列。 输出 One line with n intergers, which are theorder of a tree that generate the same tree with the least lexicographic. One line with n intergers, which are theorder of a tree that generate the same tree with the least lexicographic一行带 n 个整数，它是生成同一棵树的树的顺序，这棵树具有最少的字典形式。
给一个序列，依照序列建二叉排序树，输出建成这棵树的最小字典序列。 样例输入1 4
1 3 4 2 样例输出1 1 3 2 4
3508 题目描述 Hardwoods are the botanical groupof trees that have broad leaves, produce a fruit or nut, and generally godormant in the winter.
America's temperate climates produce forests with hundreds of hardwoodspecies -- trees that share certain biological characteristics. Although oak,maple and cherry all are types of hardwood trees, for example, they aredifferent species. Together, all the hardwood species represent 40 percent ofthe trees in the United States.
On the other hand, softwoods, or conifers, from the Latin word meaning"cone-bearing," have needles. Widely available US softwoods includecedar, fir, hemlock, pine, redwood, spruce and cypress. In a home, thesoftwoods are used primarily as structural lumber such as 2x4s and 2x6s, withsome limited decorative applications.
Using satellite imaging technology, the Department of Natural Resourceshas compiled an inventory of every tree standing on a particular day. You areto compute the total fraction of the tree population represented by eachspecies.
阔叶树是一类植物，叶子宽阔，结果实或坚果，通常在冬季休眠。美国的温带气候产生了数百种硬木树种的森林——这些树种具有某些生物学特性。虽然橡树，枫树和樱桃都是硬木树种，例如，他们是不同的种类。总的来说，所有的硬木树种占美国树种的40% 。另一方面，软木，或针叶树，从拉丁语意为“圆锥轴承”，有针叶。广泛可用的美国软木包括雪松，冷杉，铁杉，松树，红木，云杉和柏树。在家里，软木主要用作结构木材，如2x4和2x6，一些有限的装饰应用。利用卫星成像技术，自然资源部编制了一份特定日子里每棵树的清单。你要计算每个物种所代表的树种总数的分数。
输入 Input to your program consists ofa list of the species of every tree observed by the satellite; one tree perline. No species name exceeds 30 characters. There are no more than 10,000species and no more than 1,000,000 trees. 程序的输入包括卫星观察到的每棵树的物种列表; 每行一棵树。物种名称不得超过30个字符。这里的物种不超过10000种，树木也不超过100万棵。 输出 Print the name of each speciesrepresented in the population, in alphabetical order, followed by thepercentage of the population it represents, to 4 decimal places. 以字母顺序显示每个物种的名称，然后显示该物种占该物种总数的百分比，最后以小数点后4位显示。
样例输入1 Red Alder
Ash
Aspen
Basswood
Ash
Beech
Yellow Birch
Ash
Cherry
Cottonwood
Ash
Cypress
Red Elm
Gum
Hackberry
White Oak
Hickory
Pecan
Hard Maple
White Oak
Soft Maple
Red Oak
Red Oak
White Oak
Poplan
Sassafras
Sycamore
Black Walnut
Willow 样例输出1 Ash 13.7931
Aspen 3.4483
Basswood 3.4483
Beech 3.4483
Black Walnut 3.4483
Cherry 3.4483
Cottonwood 3.4483
Cypress 3.4483
Gum 3.4483
Hackberry 3.4483
Hard Maple 3.4483
Hickory 3.4483
Pecan 3.4483
Poplan 3.4483
Red Alder 3.4483
Red Elm 3.4483
Red Oak 6.8966
Sassafras 3.4483
Soft Maple 3.4483
Sycamore 3.4483
White Oak 10.3448
Willow 3.4483
Yellow Birch 3.4483 提示/说明 This problem has huge input, usescanf instead of cin to avoid time limit exceeded. 标签 普及+/提高 其他 二叉搜索树，BSTSTL
| 
发表于 2023-3-27 19:00:30
置顶卡
发表于 2023-3-28 18:56:51
楼主
