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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

记NOI2010  

2010-08-05 15:44:12|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
时间过得如往常一样快,NOI2010即将过去了。(明天凌晨2:00离开烟台)
记忆中许多碎片被定格。

是坐火车去的,票很紧张,北京队只搞到了不同车厢的一堆上铺。
虽然是一群喜欢写程序的人一起出来,但主要的娱乐活动还是三国杀+变色龙。
即将在列车上睡觉的时候,我看着很令人感到压抑的天花板,思考区间众数查询的问题,
想出了一个时间复杂度O(N^1.5)(默认查询的数量是O(N)级别的)的算法,并且证明了zkw的变态算法
不会比这个算法快。
我的算法:1.对于出现次数较多的数,以数为主元进行枚举。2.对于出现次数少的,以答案为主元进行枚举。

刚刚到烟台安顿好,Day0就开始了。笔试向往常一样遭到“鄙视”,“贪玩的明明”“聪明的明明”这两道题也没啥人做。
我还是好好研究了一下Day0的提交答案,深感时间过于紧迫,没办法好好做。
当我带着笔试100这个“大众分”欣喜地回到宿舍的时候,突然意识到:明天就是Day1。
其实这是一个很显然的事情,但不知怎么,它让我有一种不真实感。

Day1,早上,被手机按计划叫醒。从我醒来的那一刹那开始,我觉得我的消化系统就按惯例开始不正常工作。
结果呢?就是Day1在饿着肚子的状态下考完了。今年提供的食品袋里竟然有卫生纸,不过“能量食品”少了点,估计
是没有考虑到我这种人。
看到题目,忽然觉得,和去年看到题目时有了一种不同的感觉。在集训的时候,我曾经总结去年失败的教训就是“每道题都只想骗30分走人”然而,我觉得,今年的题明明是可以每道题“骗90分走人”!一个计数,一个朴素的数据结构,一个有点想象力的最小割。我惊叹于每道题我都有“想法”。第一题的朴素算法和第二题的完美所发首先被我“清扫”,之后是第三题默写了一个网络流。由于第3题的数据规模有点大,我想我写的dinic顶多过6个点,剩下的多半是出题的神牛打算介绍他的“稀疏图专用网络流算法”。第一题呢,80分朴素过于好写了,但还想多那哪怕1个点都是要把整个算法颠覆一遍才行。
这时还有2个小时,我把已经写好的程序都和朴素对拍了一边,感到有点无所事事了。无所事事,这怎么行?
那就从第2遍代码"review"开始吧。虽然通过了对拍,但代码里还是颇有几个“钉子”的。可是code review很快就结束了。听着满场霹雳啪啦的键盘声,我决定:开始骗分!唯一可能有“油水”的就是第一题倒数第2个点。我想起了集训时神牛“别忘打表”的启示,写了一个分段打表的程序。这时,听见组织者说“代码限制100K”,我明白有很多人和我用了相同的算法。
中午,评测,下午,复测,讲题。我看了一眼分,250,很淡然,因为是意料之中的了。第一题,打表成功,90分。完美算法实际上是基于基本的容斥原理,可惜了,我没有碰过类似的题目,所以没有想到。现在好了,听明白zf的讲解,我的“算法工具库”中又多了一个专门对付“约数统计类”题目的工具。第二题嘛,莫名其妙地wa了3个点,可能是某些很rare的bug没有被我抠出来。正规算法和我想的几乎一模一样,当然,也有其他稀奇古怪的做法ac的。第三题,神奇dinic跑出了9个点(北京队其他用此网络流算法的同学得分参差不齐)。没有我想象中“稀疏图专用网络流算法”,而是“平面图专用网络流算法”,即把问题转化为对偶图上的最短路。听福建那边说有人讲过。
总体来说,有些遗憾,但我也接受了,毕竟好于预期。

Day1过后,是游玩的日子。
下午,海滩。
我很喜欢海,虽然我不喜欢游水。甚至,我都不是很喜欢走进海浪里。海吸引我的,还是那种坐在沙滩上静静地看着浪花一波又一波涌来的感觉。人还不算多,所以海就还算清。风一阵阵柔和地吹来,波涛发出极富韵律感的声音。一群蜻蜓无声无息地集体飞了过来,在海上逗留一阵,就无声无息地飞走了。北京队的几名同学走进了大海里欢乐,在岸上,更多的人像我一样坐在沙滩上,呆呆地望着远方。
玩点什么吧,我突然想。
于是,我取来几个贝壳,在细沙上刻划图案。不知怎的,我静静地在沙滩上挖出了一个"NOI"的字样,然后蹲坐在旁边,默默看着流动的细沙一点点把它变得模糊不清。

Day2就要到了。按惯例,我到poj上刷题一道来找状态。然后,按惯例早早睡觉。
我的密码条上印的密码是“kowvic”,被一些同学附会为"cow victory",说是“天降吉兆”。我表示窘迫。
也许我在睡梦中根本没有预见到,Day2是一场怎样艰苦的斗争。

早上消化系统感到极端恶心。我几乎是空着肚子走到了机器旁。深呼吸,登录,调整字体,这一切都是按惯例。
之后,我拿起了题,有些意外的,发现我又是都有想法。一个图论+构造,一个状态压缩dp,一个提交答案乱搞。
我试图按照设想从第2题——我最拿手的dp类题目开始。虽然算法很显然,但是具体细节非常多,实现很复杂。
结果,2个小时过去了,我的代码还是一盘散沙,一盘4K的散沙。我彻底感受到了这题的变态之处,但是,已经晚了。
还剩3个小时,从0开始,基本上是已经到了绝望的边缘,我该怎么办?
我用5分钟调整了一下思绪,看了看其他两题,果断做出一个决定:放弃第2题,但决不放弃今天的比赛。
第1题,我快速想出了第一问以及第二问的前6个点。不敢再多花时间,速速编码,飞速调试。
第3题,我推导了一会儿公式,写了一个很朴素的贪心。经过计算,我有把握拿64分。
这时,只剩下1个小时了。不过,我已经确保可以拿到140分来垫底。
该干什么了呢?我看着第2题,决定放弃完美算法,快速写出特殊数据的朴素解法。即使是朴素解法,也够恶心,需要大量分类讨论。
这时平常练的简洁代码术发挥了巨大作用,各种trick让代码量*=0.25   还剩5分钟时,可算调试完毕。镇定地进行了最后一边检查,
我坦然的,离开了考场,拒绝和任何人讨论试题。

Day2的中午我过的很平静,因为我从没有给我自己设想过什么。Day1的250分排第14名,足以保证银牌线了。至于金牌,我明白,它归谁是命运说了算的。我,只不过是执行命运的实体。
测评结果,172,第一题有两个点掐时失败,估计是测评机比较奇特(我自己跑半秒就出来了,申请复评,但是没有成功)。
银牌线,270;金牌线,379。
我带着一丝意外,一丝欣慰,跑回宿舍休息了。
在报告厅,听说某些同学看到成绩后泪如雨下。

团体对抗赛北京向来是被虐的,今年也不例外。早早的,我们就退场了。
度过了无聊的几个小时,接下来是颁奖会,然后是回北京。

然后呢?没有然后了。
暑假还剩一小半,过几天就是分班考试,还有开学前的军训。
总之,NOI2010过去了。既然已经过去,就不要再留恋了。
带着微笑,望向明天。
  评论这张
 
阅读(1408)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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