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

 
 
 

日志

 
 

HNOI 2012 Day1 双十字 ( BZOJ 2727 ) 前缀和的加强版用法  

2014-01-24 08:55:49|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
首先 这道题的难点绝对不是数据结构优化什么的
然后 如果没有做过 BIT实现POJ3468 的话 最好还是先做做
我前段时间做过这题 但没完全搞懂 不过现在理解了不少
-------------------------------------------------------------------------------------------
先说最容易想到的方法
枚举每一列上的两个“十字点” 这样的话是O(C*R^2)
根据存储方式以及细节的不同 可拿60-90(我只有60 QAQ)
-------------------------------------------------------------------------------------------
然后就是正解
只枚举每一列下面那个“十字点”上面的可通过前缀和思想+BIT统计
(枚举对象很重要啊)
这样的话是O(C*RlogR)
所有的点都可以在1s内解决
由于我是看VFK的题解改的 所以BZOJ评测时间和VFK差不多
可是他的空间为何只有我的1/6啊
-------------------------------------------------------------------------------------------
或许前面说得太抽象了 下面讲具体点
开三个BIT
BIT 1 维护当前每种长度的“十字点”的个数
BIT 2 维护当前每种长度的“十字点”的长度和
BIT 3 维护当前每种长度的“十字点”的长度和的前缀和
          (注意是逆向的 比如 5+4+3+2+1 s[1]=5 s[2]=9 s[5]=15)
维护的东西都讲了 查询操作就不讲了
不懂的话 请做一遍 BIT实现POJ3468
-------------------------------------------------------------------------------------------
  评论这张
 
阅读(113)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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