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

qus的博客

 
 
 

日志

 
 

TOPCODER SRM 471 (久违的解题报告)  

2010-05-27 22:40:20|  分类: 原创 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

发现已经很久没有写解题,也是因为做题少了很多呢...

因为有道快开始了,为了复赛的实习通道必须努力打进复赛啊。所以,今晚,去练习房做了次topcoder SRM471。

250分的,题意很简单,就是定义了一条质数链,问指定范围内,的最大质数链。

筛一次质数,再从2推回N,求一次。本来算法是很简单的,但是,N达到1000W,令我各种奇形怪状的算法,例如什么MAP优化质数表啊等等的。不过TLE到死。分数也降到不能再降得75...最后,暴力原始算法,终于过了SYSTEM TEST。看了看运行时间,极限数据才900+MS...囧

500分题目,给一个连接矩阵,求一条最短路,满足任意一段的时间和不能被13整除。

用优先队列搜索,每个状态保存,当前城市,长度13的余数数组,当前状态的耗时。哈希判重。状态总数(1<<13)*25,每次拓展25。

算法不难想,不过代码,十分不熟练,交上去300分。

1000分题目,给最多50条线段,令线段首尾相接,使头尾两点最远。

题目,可以简化为每个线段是取正还是取反,然后将x,y,z都加起来,求出X*X+Y*Y+Z*Z的最大值

总搜索空间达到2^50

第一反应是模拟退火算法,不过,未写过退火的转移,于是,直接按间隔,给出初始状态。

算法,如下:

枚举begin从0到(1<<n) ,间隔取(1<<n)/ti,ti为模拟退火次数

然后,每次锻炼的时候,枚举50个线段看取反能不能获得更大值,能就更新,直到不能再更新。

一开始,对时间复杂度估计不足,取了ti为10W。超时,下了数据来本地跑,返现根本出不了解。修改ti到5000才能出解。

然后,交上去就过了。

十分感动啊,知道了模拟退火算法N年了,终于写出第一个模拟退火算法啊!!!

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

历史上的今天

评论

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

页脚

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