集训队作业poi188道解题报告poi18rot

1、POI18rot 解题杭州学军中学题目简述有一棵 n 个结点的二叉树，每个叶子结点有一个不同于别的结点的。每次操作可以交换一个结点的左右。定义这棵树的导出序列是这棵树的叶子结点的从左向右形成的序列。经过任意操作之后，希望导出序列的逆序对数目最少。输出最少的逆序对数目。n 200000算法分析递归处理每棵逆序对一个在 A，假设它两个，一个在 B是 A、B。只要考虑的逆序对（即的情况）就行了，不的逆序对可以递归处理。算出 A 在左 B 在右产生的逆序对，再算出 B 在左 A 在右产生的跨越逆序对，挑个产生逆序对少的方式合并。关键是两步操作：1. 找出A、B 的逆序对的个数2. 合并 A、B。可以发

2、现，这和求逆序对的归并算法很类似。归并法求逆序对的方法是这样的：将当前数列等分为两个序列，对这两个序列分别递归处理，排序并得到的逆序对个数，然后合并两个有序序列并且统计的逆序对个数。合并两个有序序列并统计的逆序对个数这一步的时间复杂度是()的，所以() =2 ( ) + ()。得到() = ( log )。2但是这道题不能这样做，原因是不能将当前数列等分为两个序列，是根据当前结点将左右分成两个部分递归处理的，并不能保证大小上是等分的。如果这棵树很不平衡，会导致递归()层，每层时间复杂度()，最终会为(2)。递归()层似乎不可避免，关键是处理每层时的时间复杂度。可以考虑用平衡树中的所有叶子结点。

3、做第一步“找出A、B 的逆序对的个数”的时候枚举小的那个，找大的那个中和它产生逆序对的个数。用(min (), () log max (), ()的时间。合并 A、B 的时候，将小的那个平衡树的点一个个到大的那个平衡树中，也就是平衡树的启发式合并。用的时间同上。每个点最多(log )次，每次用的时间(log )，所以总复杂度是( log2 )。可以解决此题。原题Tree RoionsMemory limit: 64 MBByteasar the gardener is growing a rare tree called Rosomeeresting features:us Informati

4、kus. IsThe tree consists of straight branches, bifurcations and leaves. The trunk stemming from the ground is also a branch.Each branch ends with either a bifurcation or a leaf on its top end.Exactly two branches fork out from a bifurcation at the left branch and the right branch.of a branch -Each l

5、eaf of the tree is labelled wi labels of leaves are unique.neger from the range. TheWith some gardening work, a so called roion can be performed onany bifurcation, swapthe left and right branchest fork out of it.The corona of the tree is the sequence of leaves labels from left to right.egers obtaine

6、d by reading theByteasar is from the old town of Byteburg and, like all true Byteburgers, praisesneatness and order. He wonders how neat can his treeenks toappropriate roions. The neatness of a tree is measured by the numberof inverts in its corona, i.e. the number of pairs,suchhe corona.The origina

7、l tree (on the left) with coronahas two invers. A singleroion gives a tree (on the right) with corona, which has only oneinver. Each of these two trees has 5 branches.Write a programt determines the minimum number of invershecorona of Byteasars treet can be obtained by roions.Inputhe egerline of the

8、 standard input there is a single()t denotes the number of leaves in Byteasarstree. Next, the description of the tree follows. The tree is defined recursively:if there is a leaf labelled with() atof the trunk (i.e.,the branch from which the tree stems), then the trees descriptionconsists of a single

9、 line containing a singleeger,if there is a bifurcation atof the trunk, then the treesdescription consists of three parts:o theline holds a single number ,then the description of the left subtree follows (as if the left branch forking out of the bifurcation was its trunk),and finally the description

10、 of the right subtree follows (as if the right branch forking out of the bifurcation was its trunk).ests wort least 30% of the pos it additionally holdst.Outputheand only line of the standard output a singleeger is to be pred:the minimum number of invershe corona of the input treet can beobtained by a sequen