注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1078: [SCOI2008]斜堆  

2014-05-23 19:46:00|  分类: oi,bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1078


发现某一个子树的序列可以由左右子树合并得到,那么就恶心的分类讨论一下合并的方案即可。


代码:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  • #include <vector>
  •  
  • using namespace std ;
  •  
  • const int maxn = 110 ;
  •  
  • int left[ maxn ] , right[ maxn ] , n ; 
  •  
  • inline vector < int > dfs( int now ) {
  •     vector < int > l , r , t ; 
  •     l.clear(  ) , r.clear(  ) , t.clear(  ) ;
  •     if ( left[ now ] ) l = dfs( left[ now ] ) ;
  •     if ( right[ now ] ) r = dfs( right[ now ] ) ;
  •     if ( ! l.size(  ) && ! r.size(  ) ) {
  •         t.push_back( now ) ;
  •     } else if ( ! r.size(  ) ) {
  •         if ( l.size(  ) > 1 ) {
  •             t.push_back( now ) ;
  •             for ( int i = 0 ; i < l.size(  ) ; ++ i ) t.push_back( l.at( i ) ) ;
  •         } else t.push_back( l.at( 0 ) ) , t.push_back( now ) ;
  •     } else {
  •         int i , j ; 
  •         for ( i = 0 , j = 0 ; i < l.size(  ) && j < r.size(  ) ; ++ i , ++ j ) {
  •             t.push_back( l.at( i ) ) ; t.push_back( r.at( j ) ) ;
  •         }
  •         if ( i < l.size(  ) ) {
  •             if ( i == l.size(  ) - 1 ) {
  •                 t.push_back( l.at( i ) ) ;
  •                 t.push_back( now ) ;
  •             } else {
  •                 t.push_back( now ) ;
  •                 for ( ; i < l.size(  ) ; ++ i ) t.push_back( l.at( i ) ) ;
  •             }
  •         } else if ( j < r.size(  ) ) {
  •             t.pop_back(  ) ;
  •             t.push_back( now ) ;
  •             for ( -- j ; j < r.size(  ) ; ++ j ) t.push_back( r.at( j ) ) ;
  •         } else t.push_back( now ) ;
  •     }
  •     return t ; 
  • }
  •  
  • int main(  ) {
  •     memset( left , 0 , sizeof( left ) ) , memset( right , 0 , sizeof( right ) ) ;
  •     scanf( "%d" , &n ) ;
  •     for ( int i = 1 ; i <= n ; ++ i ) {
  •         int d ; scanf( "%d" , &d ) ;
  •         if ( d >= 100 ) right[ d - 100 ] = i ; else left[ d ] = i ; 
  •     }
  •     vector < int > ans = dfs( 0 ) ;
  •     for ( int i = ans.size(  ) - 1 ; i >= 0 ; -- i ) printf( "%d " , ans.at( i ) ) ;
  •     printf( "\n" ) ;
  •     return 0 ; 
  • }



  评论这张
 
阅读(3)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018