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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2809: [Apio2012]dispatching(贪心+主席树)  

2014-01-10 21:37:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


题目说的很复杂,说白了就是给你一棵树,然后选出一个节点,在该节点的子树上选取尽可能多的点,并使得选的点的权值和不到于m,明显,这里可以把所有的点取出来,按权值排序,然后从小往大取(调整法可以轻松证明),尽可能取多的点,那么这里就可以先把树处理成DFS序列,然后用主席树维护,直接在主席树上二分即可。

复杂度:O(n log n)


代码:

BZOJ-2809: [Apio2012]dispatching(贪心+主席树) - cjjlsdy - cjjlsdy的博客

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define ll long long

  • #define L( t ) node[ t ].left

  • #define R( t ) node[ t ].right

  • #define Sum( t ) node[ t ].sum

  • #define S( t ) node[ t ].size

  • #define MAXN 100100

  • #define MAXV 5000100

  •  

  • ll inf 0x7fffffff;

  •  

  • struct edge{

  •         edge *next ;

  •         int t ;

  • }*head[ MAXN ];

  •  

  • void AddEdge(int s ,int t ){

  •         edge *p =new( edge );

  •         p -> t = t , p -> next = head[ s ];

  •         head[ s ]= p ;

  • }

  •  

  • struct Node{

  •         int left , right , size ;

  •         ll sum ;

  •         Node (  ){

  •                left = right = sum = size =0;

  •         }

  • } node[ MAXV ];

  •  

  • int V =0, n ;

  • ll m , a[ MAXN ][2];

  •  

  • void Add(int l ,int r ,int k , ll v ,int u ,int&t ){

  •         t =++ V ;

  •         S( t )=S( u )+1,Sum( t )=Sum( u )+ v ;

  •         if( l == r )return;

  •         int mid =( l + r )>>1;

  •         if( k <= mid )R( t )=R( u ),Add( l , mid , k , v ,L( u ),L( t ));else

  •         L( t )=L( u ),Add( mid +1, r , k , v ,R( u ),R( t ));

  • }

  •  

  • void Init(  ){

  •         memset( head ,0,sizeof( head ));

  •         L(0)=R(0)=S(0)=Sum(0)=0;

  •         inf *= inf ;

  • }

  •  

  • struct saver{

  •         ll v ;

  •         int t ;

  •         bool operator<(const saver &a )const{

  •                return v < a.v ;

  •         }

  • } b[ MAXN ];

  • int bn , Rank[ MAXN ];

  •  

  • int dfn[ MAXN *2], cnt =0, pre[ MAXN *2], first[ MAXN ], last[ MAXN ];

  •  

  • void dfs(int v ){

  •         dfn[ first[ v ]=++ cnt ]= v ;

  •         for( edge *p = head[ v ]; p ; p = p -> next )dfs( p -> t );

  •         dfn[ last[ v ]=++ cnt ]= v ;

  • }

  •  

  • ll ans =0;

  •  

  • int main(  ){

  •         int roof ;

  •         Init(  );

  •         scanf("%d%lld",&n ,&m ); m *=2;

  •         for(int i =0; i ++< n ;){

  •                int x ;scanf("%d%lld%lld",&x ,&a[ i ][0],&a[ i ][1]);

  •                if( x )AddEdge( x , i );else roof = i ;

  •                b[ i ].v = a[ i ][0], b[ i ].t = i ;

  •         }

  •         b[ n +1].v =- inf , b[ n +1].t =0, b[ bn = n +2].v = inf , b[ n +2].t =0;

  •         sort( b +1, b + bn +1);

  •         for(int i =0; i ++< bn ;) Rank[ b[ i ].t ]= i ;

  •         pre[0]=0;

  •         dfs( roof );

  •         for(int i =0; i ++< cnt ;)Add(1, bn , Rank[ dfn[ i ]], a[ dfn[ i ]][0], pre[ i -1], pre[ i ]);

  •         for(int i =0; i ++< n ;){

  •                ll rec = m , num =0;

  •                int t0 = pre[ first[ i ]-1], t1 = pre[ last[ i ]], l =1, r = bn ;

  •                while( l < r ){

  •                        ll ret =Sum(L( t1 ))-Sum(L( t0 ));

  •                        int mid =( l + r )>>1;

  •                        if( ret <= rec ){

  •                                rec -= ret , num +=S(L( t1 ))-S(L( t0 ));

  •                                t0 =R( t0 ), t1 =R( t1 ), l = mid +1;

  •                        }else{

  •                                t0 =L( t0 ), t1 =L( t1 ), r = mid ;

  •                        }

  •                }

  •                ans =max( ans ,( num /2)* a[ i ][1]);

  •         }

  •         printf("%lld\n", ans );

  •         return 0;

  • }



  评论这张
 
阅读(7)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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