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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

说说NOIP2012的题  

2012-11-19 22:10:59|  分类: OI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

再次围观OI比赛了。


今年NOIP的题值得赞美。我对它的概括为:很实惠,有新意有难度

第一天
第一题 vigenere。简单密码的解密。
北京一共192人,其中满分143人。
不用说了。

第二题game
这是一个很“实惠”的题目。
它是寻找一个排列P,最小化:
max(product(A[P[i]] for i in range(a))/B[P[a]] for a in range(0,n))
这种题对于受过良好数学/信息学系统训练的同学来说,是非常简单的。
但对于其他竞赛选手来说,就比较难了。
我们只要考虑将序列中的相邻两个人交换会发生什么即可:
  S   a      c
     ---    ---
      b      d
设前面人左手上的数字积是S。
原来的式子是:max(S*a/d,S/b)
交换之后的式子是:max(S*c/b,S/d)
什么时候max(S*c/b,S/d)<=max(S*a/d,S/b)?
考虑到a,b,c,d>=1
稍微化简一下,就知道了:当a/d>=c/b,或者说a*b>c*d。
这样,问题瞬间解了:按照每个人左右手的乘积排序即可。
这题实惠的地方还体现在,只有对信息学有特殊爱好的人才会去写高精度。。。

第三题drive
这题很有新意。新意在于,把数据结构引入了NOIP这种“大众”的比赛。
题目很复杂。
不过做法很直接。首先先用set暴力把每个城市对于A和B来说的后继找到。
找到后继之后,这个图实际上变成了一个森林。
之后,用你最喜欢的维护树的数据结构把问题回答了即可。
这种题是选手毅力和实力的体现。我欣喜的看到北京还是有两个同学ac的。(虽然他们都是老选手了。。。)


第二天

这天的题目比较难。
第一题:解一元一次同余方程。
这个是送分题,看看你学过OI没有。

第二题:维护区间最小值,支持区间减少。
这个是数据结构送分题,把“业余”的竞赛选手和“专业”的区分开了。

第三题:
这个稍微难一点了。
一个树,你在树上有若干个军队。军队可以占领他在的节点。军队沿树边移动需要时间。(不同军队可以同时移动)。
问最少的时间,使得从根到每一个叶子的路径上至少有一个军队。根不能被占领。

说来,这题我也是要思考一会儿的。
首先,军队肯定不从父亲走到儿子,只会从儿子走到父亲。唯一的例外:从根往下走。
这样,我们二分答案,之后,军队一起往根走。
如果走不到根呢?就停在那里吧。
之后我们观察根的每一个子树。
有两种事情:
这个子树里至少有一只军队能够走到根。 (出口型子树)
这个子树还没有被他内部走不到根的军队搞定。(进口型子树)
注意,一个子树可以同时进口又出口。
这样,问题就变成了能出口的军队和所有进口型子树之间的匹配问题。
这个匹配硬解是不可以的。
我们要贪心。
对于一个出口型子树,如果他同时是一个进口子树,并且用了一个可出口的军队来解决自身,那么一定用的初始位置最深的那个。
如果这个“保留军“到达根之后无法返回他来自的子树的根,那么可以证明,他肯定就不用出口了。留在根的儿子好了。
这样,我们可以安心的把所有的军队调到根。
然后,把还没有解决的子树和军队的剩余时间排序,比比大小。
问题就解了。

似乎很繁琐。不过还是很有意思的。
有难度。我喜欢。
  评论这张
 
阅读(3446)| 评论(10)
推荐 转载

历史上的今天

评论

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

页脚

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