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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 189 Div1 & Div2  

2013-06-25 15:28:52|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
开小号做div2。。。喜闻乐见掉了。。
如果我进了集训队。。
我就打到红名去!
==============================================
div2的题真心没啥意思。。。几乎都是一眼题。。
只可惜考试的时候E题,b了好久。。。。遗憾啊
==============================================
div1的题嘛。。。其实也木有啥意思。。难度不大
D题:
字符串
每次选择最小的一个重复子串(多个的话选择最右边的那个)缩成一个。。求最终的字符串
比如aa->a
方法:
显然选择的重复子串只会越来越大。。
枚举这个Len。。Len递增。。
找长度为Len的重复子串的算法是很喜闻乐见地可以做到n/Len的。。经典问题
如果存在长度为Len的话,我们就O(n)将所有长度为Len的重复子串缩掉
由于不同的Len至多O(sqrt(N))个。。所以时间复杂度是O(Nsqrt(N))了。。还算比较碉堡的思路。。但代码挺好写

E题:
div2的B题的加强版。。
(a,b)往(c,d)连边的条件是
(c<a<d) || (c<b<d)
每次加入一条线段。。线段的长度递增
或者
询问是否有从线段a到线段b的路径

问题的关键是。。。
我们发现两条线段相交而不包含是可以并在一起的。。
并完后。。
那么点a连向点b只可能ab已经并到一起了或者a被b包含。。
接下来我们就是要想办法将相交的东东连起来。。
显然不能处理处所有的相交关系。。。
我们yy一下
发现相交了的话就将其并起来。。
由于发现线段只会扩大。。无视掉包含。。那么并起来与自己相交意味着一定存在一条线段与自己相交。。
所以可以线段树了。。代码我写得好丑。。。
无力吐槽。。我太弱了
  评论这张
 
阅读(425)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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