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

 
 
 

日志

 
 

HNOI 2009 Day1 梦幻布丁 ( BZOJ 1483 ) 链表的启发式合并  

2014-01-21 11:16:31|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
---------------------------------------------------------------------------------------------------------------------------------------
自己第一遍做的时候只会普通链表(上界O(MN))过5个点
也想过树形结构将N变为logN来做 不过还是不会实现
不过后来改变存储方式后也过了(400ms左右) 同时加上多个相同的连在一起只保留一个 也是不错的优化
但是数据较弱 优化反而增大了常数。。。。
然后搜题解看到了 启发式链表合并 不懂 不过看HLworld的讲解还是懂了
以下为转载内容
---------------------------------------------------------------------------------------------------------------------------------------
看到启发式合并,许多人都只会想起并查集,没有启发式合并的并查集大概是 反阿克曼函数级的最坏logN,加了之后最坏就没有logN了。

但其实不止并查集可以用启发式合并,

HNoi2009 梦幻布丁

1:将两个队列合并,有若干队列,总长度为n,直接合并,最坏O(N),

2:启发式合并呢?

每次我们把短的合并到长的上面去,O(短的长度)

咋看之下没有多大区别,

下面让我们看看均摊的情况:

1:每次O(N)

2:每次合并后,队列长度一定大于等于原来短的长度的两倍。

这样相当于每次合并都会让短的长度扩大一倍以上,

最多扩大logN次,所以总复杂度O(NlogN),每次O(logN)。

所以说,启发式还是比较好用的。
---------------------------------------------------------------------------------------------------------------------------------------
还有转载的pouy94的部分

题解:

将同色的布丁用链表保存,并统计出一开始的答案Ans = ∑ord(a[i] <> a[i – 1]) 对于变色操作(x,y),若链x长于链y则交换x,y且以后遇到x时要替换成y,遇到y时替换成x 然后扫描链x,从Ans中减去与x有关的部分,再次扫描将其颜色改成y,再次扫描给Ans中加上与其有关的部分,最后将链表x接在链表y上即可。对于询问操作直接输出Ans即可

 

这篇题解是mt留下来的,精炼而直切要点~~

 

多说一点,关于这个算法的复杂度,每次操作是均摊O(logn)的

证明的话,可以这样想,由于是将小的并到大的里头去,所以最麻烦的情形就是合并两个等长的链表,也就是说,对于每一个布丁,每对他操作一次就会使它所在的链表长度*2,那么最多对每个点操作O(logn)次,也就是每次操作均摊O(logn),所以整个算法的复杂度就是O(mlogn)了

---------------------------------------------------------------------------------------------------------------------------------------

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

历史上的今天

评论

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

页脚

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