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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

北京2012冬令营Day2试题大意及算法  

2012-01-20 19:07:25|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这两次的题目下载:

感谢陈高远出的题。他出的题的质量很高,数据也很负责。
陈高远说,他出题没有思路,于是。。。看了一部叫“魔法少女小圆”的动画。。。于是就有思路了。
整体来说,题目难度是“限制级”的(就是因政策原因而不是很难)。

第一题:冷冻
一张无向图,问从S到T的最短路,其中可以使用K此魔法使某条边的长度减半(魔法不能叠加)。
N,K<=50

第二题:灵魂宝石
有N个少女,每个少女有一个对应的宝石。如果一个少女到她对应的宝石的距离小于R,那么她就被控制了;如果到对应的宝石的距离大于R,就不被控制;如果到对应宝石的距离等于R,那么就可能被控制也可能不被控制。
已知N个少女和宝石的坐标,并且有K个少女被控制。但是不知道少女和宝石之间的对应关系。问:R的最大值、最小值分别是多少?
N,K<=50

第三题:孵化者
给一个上下文无关文法,问一个串是否被接受。串长度<=20。


先说说分数吧。
我280,丢脸的最高分。。。
剩下的好像有些240(罗剑桥考的不错),200+有一些(人大附中的孩子考的不错),100+有一些。

算法呢?
第一题:
经典dijkstra,把图拆成K+1层,一个层内部是正常的,从一个层到上层的对应点的邻居可以只用一半的费用。随便过。

第二题:
二分出一个最小的R,使能够有K个少女被控制(即,少女和宝石之间的最大匹配数达到K),这个就是R最小值。
二分一个最大的R,使能够有N-K个少女不被控制(即,少女和宝石匹配的补的最大匹配达到N-K),这个就是R最大值。
至于这个最大、最小的关系为什么对呢?意识吧。。。想象这个“有机数学”反应的过程,那个晴天霹雳的时刻,肯定能找到K个匹配的少女。
我在这题上丢了20分!原因是:
陈高远较劲脑汁卡精度,使得我这种直接对R进行二分(而不是对R^2,坐标都是整数)的人挂。
我写的代码:
while (r-l>1e-4){
 if ... r=(r+l)/2;
 else l=(r+l)/2;
}
在四舍五入输出两位小数的时候挂了。。。。因为,有一个点的答案是类似
sqrt(1504^2+1997^2)=2500.0049999950000099999750这样的数。。。1e-4不够!
这题正解是二分R^2,或者十分小心的二分,或者,暴力100轮二分。

第三题:
经典算法啦,一个高次的dp,好像叫CYK算法,有兴趣的自己了解吧。

陈高远讲题的时候顺便说了说形式语言的事情,我觉得挺有意思的。


北京冬令营结束了,一共20%的分数尘埃落定。
同学们加油啊(尤其是lsh、wgr,赶紧多做题!)
  评论这张
 
阅读(1606)| 评论(8)
推荐 转载

历史上的今天

评论

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

页脚

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