首页 > 其他 > 详细

codechef 2014FebChallenge

时间:2014-02-18 08:22:56      阅读:423      评论:0      收藏:0      [点我收藏+]

  

LCPESY   SUBMIN   TWODOGS       水题

 

COLARR           贪心

 

DRGHTS           dfs找联通块

 

LMATRIX2         注意到k可以较大,用线性模方程做效果较好。但我不会优化,所以只搞了0.8多。OrzACRush再次杠榜(有ACRush做Challenge还想拿高分?)。

 

LEMOVIE          dp 暴力O(N^3)显然。然后没去想优化。。

 

CHSEQ22         可以看出是一个类似求xor基元的东西,由于都是区间,从小到大每次将头相同的尾最小的拿出来,将其他与其头相同的消掉,注意到维护的只是尾部的最小值,用可并堆即可。

 

DAGCH    知道dominator tree就会发现求的东西就是semi(半必经点)。Dfs后倒序用并查集搞。注意原图是按dfs标号的,所以dfs预处理按从小到大来。

 

COT5        orz主席。LCA是区间最大值。两点dis为从x每次跳到比它大的最后到达y的点的数量,用线段树upd的技巧可以做到nlog^2n。

codechef 2014FebChallenge

原文:http://www.cnblogs.com/oldmanren/p/3551341.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!