HDOJ 5338 ZZX and Permutations 线段树+树状数组

发布时间:2017-09-09 10:26:51 作者:上海宙翔货物运输代理有限公司
HDOJ 5338 ZZX and Permutations 线段树+树状数组





对于2 1 3 这种情况(2)(1 3)的话得到的字典序最大,所以一个数有时候也是可以跳转到自己的

ZZX and Permutations Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 775 Accepted Submission(s): 244

Problem Description ZZX likes permutations.

ZZX knows that a permutation can be decomposed into disjoint cycles(see https://en.wikipedia.org/wiki/Permutation#Cycle_notation). For example:
Note that there are many ways to rewrite it, but they are all equivalent.
A cycle with only one element is also written in the decomposition, like (1) in the example above.

Now, we remove all the parentheses in the decomposition. So the decomposition of 145632 can be 135462,462135,351462,246153,624153……

Now you are given the decomposition of a permutation after removing all the parentheses (itself is also a permutation). You should recover the original permutation. There are many ways to recover, so you should find the one with largest lexicographic order.
Input First line contains an integer t, the number of test cases.
Then t testcases follow. In each testcase:
First line contains an integer n, the size of the permutation.
Second line contains n space-separated integers, the decomposition after removing parentheses.

n≤105. There are 10 testcases satisfying n≤105, 200 testcases satisfying n≤1000.
Output Output n space-separated numbers in a line for each testcase.
Don't output space after the last number of a line.
Sample Input 2 6 1 4 5 6 3 2 2 1 2
Sample Output 4 6 2 5 1 3 2 1
Author XJZX
Source 2015 Multi-University Training Contest 4

/* *********************************************** Author :CKboss Created Time :2015年08月03日 星期一 15时51分35秒 File Name :HDOJ5338.cpp ************************************************ */ #include #include #include #include #include #include #include #include #include #include #include

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:十堰网站制作 http://shiyan.666rj.com

  • 上一篇:JSP中EL表达式无效的问题
  • 下一篇:最后一页