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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

NOI2011记行  

2011-08-16 17:17:51|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
NOI2011在长春的吉林大学举办。总体来说,这个东北城市,尤其是吉林大学还是给我们留下了很深的印象的。
第一感觉,就是宿舍条件非常艰苦。说“艰苦”是一个比较含蓄的说法。简直和北京以及南方一些省份的中学的条件都没有办法比,或许这就是吉林大学悠久历史的见证。空调不要奢望了。电扇也没有,如果你不打算自己买的话。蚊子,各种虫子爬在天花板上,少的时候十几个,多的时候几十个。我们屋使用了三个蚊香,但效果并不显著。每天睡觉前的一个重要活动就是使用各种手段消灭你能够看的到的虫子,或者在把他们消灭干净前你就累得睡着了。独立的卫生间不要想了,每层共用几个。洗澡?整个大学有一个公共澡堂,每天开放4个小时,晚饭要快点吃否则就关门了。有一些省份的选手搬到外面的宾馆住了。食物还是可以接受的,尤其是每餐都有西瓜供应。比赛场地破天荒地没有空调,而是使用了大量的冰块来降温(其实心里作用远大于实际作用)。
无视掉物质生活,这次比赛还是很充实的。我们北京的平时主要是玩游戏、写题、写团体赛(我主要是在看人写题和自己写团体赛)。联想到IOI之旅我觉得北京队还是比较有生活气息的(在泰国我们的重要娱乐活动是:想题大会)。
比赛对我来说已经是一个很平淡的事情了。第一天我估算了一下题目难度,觉得要那金牌可能要做出200分左右,于是我就死磕最后一个数据结构题,剩下的都骗骗分就是了。把该写的都写完了之后,就开始无聊地玩emacs里的游戏。想去年,第一天考完了之后还十分忐忑地想着自己的分,我真觉得自己变化巨大啊。从成绩来讲,我可能是北京队里唯一一个写了哪些点就对了哪些点的同学。其他的同学,基本上是犯了莫名奇妙的错误(例如拼错文件名什么的)。当然,张放自己估分145,实际得分200,这种变态我们无视好了。讲题会是在赛场进行的,用了一个超级大的投影屏幕。
Day1.5的旅游被梁老大取消了,因为前一天看天气预报说是中雨转大暴雨转小雨。于是我们就在宿舍里闷了一天。中午买了些肯德基外卖,预算严重超支。结果,雨并不是很大。虽说如此,我觉得其实旅游也没什么意思,不如研究点有趣的东西强(吃不着葡萄说葡萄酸?)。
张放威武霸气,Day1完了之后写程序到凌晨4:00,然后开始唱歌,把我弄醒了。之后张放酣然入睡,直到中午。

这一天我研究了一个与四色地图(团体赛的题目)有关的一个问题:
给定一张图(例如比赛用的地图),如何把它在平面上画出来,使得边尽量不相交?(这个问题的实际意义就是:我们想复盘,但需要画一个地图出来)
我听取了张放的建议,得到了一个十分有效的思路:
先计算图上两点间最短路,如果两点在图上距离是k,那么我们让这两点在平面上的期望距离是(1/N)^(1/k),设我们要把所有点放置在一个1*1的正方形区域里。定义总代价是平面上所有两点间实际距离和期望距离的差的平方的和。用随机调整法来让总代价最小化。之后,我们惊喜地发现这个图已经很靠谱了。手工调整一下就出来了。

Day2的比赛对我来说也是很平凡的。吴翼在我写第二题(他出的)的时候飘到了我身边,惊奇地发现我不到100行就把题目搞定了,感到一阵窘迫。我差不多有将近3个小时来作曹钦翔出的第3题,不过已经金牌的分数让我没有动力想下去了,于是我就写了个暴搜骗分。为了打发时间,我随机了大量数据来找可能的剪枝条件,发现了一些诡异的性质。不过事后我意识到有一个重要的点我没有想到,于是,再多的时间也是徒劳的。
Day2复测的时候叶老师就带着我去和清华签约了。而北京队的其他同学可以用“几家欢喜几家愁”来形容。罗剑桥和清华也成功签约。有的同学和人大签约了。
张放威武霸气,使用C库函数strstr把一个20分的暴力程序骗出了70分。就是靠着这个灵异的事件,他踩着分数线拿了金牌。要是上天要让张放拿金牌,谁都拦不住。颁奖会上我认识了一下今年分数比较靠前的选手,有一个同学的名字不太好念,给我留下了深刻印象(你知道怎么读“堃”吗?)让人最窘迫的就是今年金牌没有准备够,所以就不发了(怒!)。张放安慰王星怡:我们都是没拿到牌的人。

北京队乘坐两辆火车回的北京。早上到站的时候大家都挺疲倦的。有些同学以后就见不到了。。。啊。

另:我在火车上构思的一个题目:
Day2第一题道路修建的动态维护。每次修改一个边(或添加一个点)。
目前正在寻找思路中。要是我能成功解决的话。。。我相信会有用处的。
  评论这张
 
阅读(2903)| 评论(10)
推荐 转载

历史上的今天

评论

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

页脚

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