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

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

cdq分治  

2014-12-21 14:58:00|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

机房居然锁门了(我中午走之前还是开着的啊!)

于是来到了电阅。。感受到了电阅感人的配置(下个dev cpp都蓝屏,看了一下任务管理器cpu已经100%)

没法写代码只能复习一下算法了T_T

输入法也是感人的,所以有打错的求不喷

 

我们先来看道题:[Balkan2007]Mokia(被权限了真悲伤)

题解已经有了

我们发现这题的特点是:

一个询问一个询问中规中矩做下来 问题很难解决

后面的询问只跟前面的操作有关(这应该是大多数题目的通性吧,不操作怎么会变化……)

合并两段操作可以在可以接受的时间内解决。

 

于是,我们想到一个想法,只考虑询问

把询问全读进来

用一个函数solve(l,r)表示解决了[l,r]之间的所有询问

 

solve(l,r)过程一般是这样的:

先递归解决[l,mid]

计算[l,mid]~[mid+1,r]部分的影响

再递归解决[mid+1,r]

 

至于如何计算影响根据题目自身的特点而定。

然而这也是最让人头痛的地方T_T

 

我比较弱,说错了求不喷QAQ

  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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