TOP

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

2015-11-21 00:56:06 来源: 作者: 【大中小】浏览:1次

[题意]:

给一个排列加上表示循环的括号,问如何让1到n的对应的字典序最大.

从1开始贪心每个数字可以往三个地方走,右边第一个,跳转到左边的某一个,和自己构成循环

对于走到右边第一个的情况,只要判断右边的那个有没有被占据就可以了,如果可以和右边的互换,那么需要在线段树中将右边的数置为0

跳转到左边的某一个,一个数如果跳转到左边的某一个则说明左边的那个是括号开头这个数是括号结尾,用一个线段树查询区间里的最大值,由于括号间是不能重叠的,所以需要用树状数组二分一下左边界.如果这个数是要跳转到左边的某个数,则要对右括号的位置在树状数组里+1,表示这里已经有一个完整的括号了

对于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:
145632=(1)(35)(462)=(462)(1)(35)=(35)(1)(462)=(246)(1)(53)=(624)(1)(53)……
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
             using namespace std; const int maxn=100100; int n; int nb[maxn],wz[maxn]; int sed[maxn<<2]; int mx[maxn<<2]; #define lrt rt<<1 #define rrt rt<<1|1 #define lson l,m,lrt #define rson m+1,r,rrt void push_up(int rt) { mx[rt]=max(mx[lrt],mx[rrt]); } void push_down(int rt) { if(sed[rt]) { mx[rrt]=mx[lrt]=0; sed[rrt]=sed[lrt]=0; sed[rt]=0; } } void build(int l,int r,int rt) { sed[rt]=mx[rt]=0; if(l==r) { mx[rt]=nb[l]; return ; } int m=(l+r)/2; build(lson); build(rson); push_up(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return mx[rt]; push_down(rt); int m=(l+r)/2; int ret=0; if(L<=m) ret=max(ret,query(L,R,lson)); if(R>m) ret=max(ret,query(L,R,rson)); return ret; } void update(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { sed[rt]=1; mx[rt]=0; return ; } push_down(rt); int m=(l+r)/2; if(L<=m) update(L,R,lson); if(R>m) update(L,R,rson); push_up(rt); } void show(int l,int r,int rt) { printf(%d: %d <----> %d mx: %d ,rt,l,r,mx[rt]); if(l==r) return; int m=(l+r)/2; show(lson); show(rson); } int ans[maxn]; bool used[maxn]; int tree[maxn]; inline int lowbit(int x) { return x&(-x); } void add(int p,int v=1) { for(int i=p;i
             
              self||right>self) { if(right>left) { ans[i]=right; used[wz[right]]=true; update(wz[right],wz[right],1,n,1); } else { ans[i]=left; /// link circle for(int j=wz[left];j
              
               ?
               ?
               ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++ 理解函数对象与lambda表达式	下一篇：HDU - 2883 kebab （最大流）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: