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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

(除草)两道cf题题解  

2014-02-19 11:54:56|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
cf的傻逼题实在太多了。。。
不过最近两场的最后一题都挺不错的。。。(不过数据太弱,两题都是随便什么傻逼做法都能过

Rockethon 2014 F
题意:最大k段子段和。。
题解:
费用流很简单。。
暴力用常数很好的堆也能把4*10^6直接过掉。。真心呵呵。。
而且O(nlogn)跑得比O(n)快。。
呵呵。
好了,O(n)的做法是这样的:
首先将负数和正数的连续子段合并,去掉两旁的负数段。。
这样就是+-+-+-+的长度为奇数的正负交错的序列。
做法是每次取出绝对值最小的那段将其和左右的两段合并。。。这样裸搞是O(nlogn)的,得用堆维护。。
但是我们可以观察出这样的性质:
假设我们要进行m次合并(合并一次减少两个数,最终只留下2*k-1个数,算算即可)。。我们可以取出当前段的绝对值前m小的那些段。从理论上来讲,这些段一定是要参与合并的——为什么呢?首先你要进行那么多次合并,但是却不是合并这前m小的,则只可能是一次合并之后得到后形成的新的数取代了之前的位置。。设第m小的段的值为S,则存在某次a+b+c<S。。则a,b,c中必有两个数的绝对值小于等于S,那么本来这儿有两次合并,现在依旧有两次合并,无所谓。还有个问题,就是你必须保证|b|<=|c| && |b|<=|a|。。也就是说,如果说有连续可合并项,还是得从小的开始搞,否则在该段就违背了之前贪心的原则了。。
这样每次至少进行了1/3m次合并。因为某次合并未进行是因为它被两旁的合并了。因为是指数级递减,次数logn,时间复杂度依旧为O(nlogn)。
但是注意到,由于前m次待选合并中至少有1/3m次有效合并,所以那么排在3m之后的那些待选合并就肯定没用了,这样每次只保留前3*m次合并
时间复杂度就是T(m)=3m+T(2/3n)=O(n)
时间是线性的,慢死人。。

round 230 div1 E
题意:
给定长度为n的串,你每次可以删除一个连续子串:1.子串中相邻两个数差为一 2.这个子串是凸的。。
删除长度为l的串得到收益为v_l(v可能为负数)。
求删除方案使得最终收益最大。。删掉一段数后,左右两旁会合起来

题解:
O(n^3)就能过了。。
做法是这样的:
首先,一次删除的数一定是先递增再递减的,而其长度可以根据其左端的数大小,右端数的大小,和最大的那个数的大小计算出来。。

所以可以这么dp:
dp[i][j]表示i到j全部删完的最大收益。
dp1[i][j]表示i到j删完,且在最后一次删除中,i是最小的,j是最大的最大收益。。
dp2[i][j]表示i到j删完,且在最后一次删除中,i是最左的,j是最右的最大收益。。

然后O(n^3)暴算即可
  评论这张
 
阅读(874)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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