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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

NOI2012记行  

2012-08-01 22:09:08|  分类: OI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今年竟然没有网络!于是,只能晚点发博客了。。。

先贴我改完的代码:

http://builtinclz.abcz8.com/showcode.php?id=2012/random.cpp

http://builtinclz.abcz8.com/showcode.php?id=2012/bicycling.cpp

http://builtinclz.abcz8.com/showcode.php?id=2012/chess.cpp

http://builtinclz.abcz8.com/showcode.php?id=2012/park.cpp

http://builtinclz.abcz8.com/showcode.php?id=2012/delicacy.cpp


省常中还是比较给力的,宿舍条件可以接受。生活用品很齐全,每餐的西瓜也是管够。不得不说他们的绿豆汤做的那叫一个好喝啊。google公司竟然提供赞助,每人都发了有google字样的水杯、夹子、笔。

开幕式的亮点之一是省常中的一个男声合唱团唱的《我是明星》,帅气的小伙子们把这首歌曲演绎的让人感动。我们北京队在day1结束之后一直在听这个歌。


练习赛的时候,我们去熟悉赛场。电脑的配置不赖(虽然没有某些比赛的时候用的那样威猛),键盘还算好用。北京队有不少同学在笔试的时候丢分了。(周天茗:“我住313房间,总分就真是313,看来笔试的丢的2分是命中注定。早知道就去你那屋住了(315)”)。


今年的题目的整体概括为:难度温和,经典度大,考察综合。

第一天:

第一题:随机数发生器

给一个递推式X[n]=(X[n-1]*a+c)%m

给定X0,求X[n]%g

n<=1e18 m<=1e18 g<=1e9

这题用做吗?!!!!!

搞一个矩阵快速幂即可。不得不说这个题延续了去年《道路修建》的送分风格。

陈高远在北京队集训的时候刚好出过一个矩阵幂的送分题,精确命中啊。


第二题:骑行川藏

给定一组正实数k[],s[],u[],

求一组正实数v[],使得sum((u[i]-v[i])**2*k[i]*s[i])<=E,最小化sum(s[i]/v[i])

n=len(k)<=10000

这是一个骑自行车的物理题,u是风速,k、s分别是风阻系数、路程,要在n段路上分配体力。

这个怎么做呢?如果你像我一样喜欢了解各种乱七八糟的东西,那么你会认同这真的是一个送分题。

拉格朗日乘数法(http://en.wikipedia.org/wiki/Lagrange_multiplier)。

解方程后发现,在最优的时候每个求和项里面dt/dE是定值。

可以利用能量的等式二分查找这个定值(需要用牛顿迭代法/二分法解方程)。

对于学习物理竞赛的人来说,这应该是一个经典题。当然,信息学竞赛考察一下高数也是挺猛的一种思路。。。


第三题:魔幻棋盘

二维矩阵,每次可以给一个区域内的的数加上一个值,或者查询一个区域(x1,y1)-(x2,y2)内的最大公约数。

保证x1<=X<=x2,y1<=Y<=y2(X和Y是给定的数)

n*m<=5e5,操作数<=1e5

不是送分题。

首先把矩阵分成四个部分,使得查询和增减都是包含顶点的。

把矩阵进行二维的差分。可以证明,差分后的区域内的最大公约数就是原矩阵的区域内的最大公约数。

之后,就可以把问题转化为:

矩阵内修改一个数、查询矩阵内一片的最大公约数。

这个是二维线段树的应用了。。。

我表示没有调出来。只能交一个四分树的暴力了,骗到80分。功力退化啊!

最终调完的满分程序达到了4.8K。太变态了。

 

第1.5天:

环球动漫嬉戏谷。

“这到底是环球,还是动漫,还是嬉戏谷?”——北京队

这个地方还是值得去的。

我们总结了嬉戏谷的精髓的最终版:商店+餐厅+影院+过山车。

分组活动,我和周天茗一直在一起。一开始,在对嬉戏谷的精髓有片面的感悟(购物+吃饭)之后,北京队集体决定往公园的一个位于山上的地方爬去。结果,在山上,我们俯瞰公园,才发现其实还是有挺多好玩的东西的。

分散开之后,我和周天茗决定去做过山车。先是从迷你版的“海盗船”开始,之后是稍微大一点的“漂流”“龙行天下”。在吃饭(我严重怀疑点心是夹生的)、看影片之后,我们望着大型的过山车“撕裂星空”,出现了奇异的对话:

“去玩那个吗?”“我不敢去。”“我也不敢去。”“别去了。”“行,别去了。”之后呢?之后,我们竟然去玩那个绝对不可能想到要去玩的东西了。

有点这种味道:甲:“我不知道你的数。”乙:“我不知道你的数。”甲:“我还是不知道你的数。”乙:“我还是不知道你的数。”甲:“我还是不知道你的数。”乙:“我还是不知道你的数。”(2008轮之后)甲:“我知道你的数了”乙:“我也知道了”。

说实话,要是命运换一个随机种子,我绝对是不敢上那个到处翻飞的大铁疙瘩的。有各种俯冲,让人几乎不敢睁开眼睛,总感觉是要撞上什么东西似的。在强大的加速度下,甚至有的时候连“啊”都喊不出来。

结果,就像每个Alice和Bob的游戏都有一个诡异的结局一样,我和周天茗竟然坐了一趟之后不过瘾,又坐了一趟“撕裂星空”。

所谓4D电影在这个乐园中得到了很好的演示。有NVIDIA的demo房间,各种有交互体验的电影,还有“3D电影+过山车+鬼屋”的神奇东西。

总之,这天我们玩的很欢乐,实际上得到了很好的放松。

不得不提到浙江队。他们在被工作人员的“诱导”下,花58元买了一壶无限续杯的饮料。结果呢?全队(坐了一整个车啊)一起“打水“。工作人员:旁边的那个饮料点也有无限续杯的。。。

 

第二天:

第一题:迷失游乐园

在至多有一个环的无向联通图里不走重复点地随机游走(就是每次随机选一个没走过的邻居走过去)。

求走的路径的长度的期望(起点也是随机的)。

N<=1e5,环长<=20

这是一个考察选手基本功的题目。算法不难,但是调试很要水平(我写了200行,调试约2H)。

树显然就是treeDP嘛。

环呢?枚举环上路径的起点、终点,之后仿照treeDP。

大部分人都得分了。虽然有些同学犯了诸多低级失误。


第二题:美食节

m个厨师提供n个菜,每个厨师做每个菜的时间是不同的。

每个菜有P[i]个消费者。要把这些订单分配到不同的厨师那里。

每个厨师一道一道的做菜。要最小化所有消费者的等待时间的和。

m<=100 n<=40 总顾客数<=800

做过的题嘛。。。

就是一个费用流的简单应用。

每个厨师的每个“位置”都对应一个点。把顾客和这些点匹配起来。厨师的第1个位置记一倍的时间,第2个位置记两倍的时间,依次类推。这样就可以表达出等待的意思了。用费用流/匹配可以做。注意使用动态加边的技巧。

点数可以做到O(n+m),边是O(n(p+m))的。

另外,经过实验,模拟退火可以骗到40分左右。。。


第三题:三重镇

http://baike.baidu.com/view/8549229.htm

就是模拟这个游戏,得尽量高的分数。

这个就是不可做的题嘛。

手工构造是满分算法。(人脑的智慧是无穷的)

我是爆搜3步,混了45分。。。。。。

顾发挥数学天赋,搞出了两个构造的点。

陈立杰随机往里面放点,据说弄出了40多分。

全场的最高分是66分。

“我们不发这个题的demo程序的原因是:这个游戏手玩太强大了。”——唐

 

最后说说成绩。

顾昱洲威武!全场第一!力压第二名(我。。。)5分!(王宏:两个IOI选手上演巅峰对决,包揽前二。我+顾:好囧)

国家队作为酱油选手上场,虐和被虐都有。

第三名是贾志鹏。陈立杰差一分上600(含笔试),收获第5。


然后该说北京队了。。。。。。

北京队啊。。。。。。

今年可惜了,没有完成2个金牌的期望目标。金、银、铜奖牌还是集齐了的。

人大附中只有一个金牌,之后2个铜牌。

不过,我们还是欣喜的看到了希望(死磕提交答案的李奇扬,通宵玩游戏的mt,对模拟退火还有数据结构有特殊情节的周天茗。。。)。

 虽然我们没有某些大牛省厉害,但是我们基本上可以做到没有悔恨。


团体赛就是一个奇葩的存在。

我们北京是以“不做不合适”的态度来看待的,小组出线是唯一的目标。

在Day2结束的晚上,大家都没有睡觉的想法,于是就熬夜玩游戏/写程序。

早上,在绝对的困倦的情况下,我们中的三个(我+罗剑桥+周天茗)到了赛场去交程序。(“你们把手机打开,如果我们人崩溃了,你们就去顶班。”)

结果呢?第一轮,浙江发飙(他们可是在排位赛里获得了事实上的垫底啊),我们竟然也混到了甲组(赛制很复杂,一时说不清,反正甲组是个好东西)。

第二轮,我强打起精神,准备如果还能出线就接着改程序。结果呢?继续出线,并且还是甲组。于是我坚定信心:不改程序了,听天由命。(浙江队无法解释的被淘汰了。。。真的,事后测评显示,这件事是一个极小概率事件!)

抽签之后,我实在撑不住了,把程序直接提交到了第三、四轮,然后回宿舍休息了。

休息了一会儿,罗剑桥打来电话:“我们进入四强了!赶紧回来看比赛!”

我冲回赛场。第4轮即将结束,我们以第2的名次出线,进入决赛。

这时,轮到决赛队伍交流经验。我还在极度困倦的状态,于是开始语无伦次。


团体赛决赛就是一个bug。

我们轮到了1/2147483648的概率的情况。

一开始,3个队伍对我们进行了围攻,结果,在躲避镜像的过程中,我们的程序出现了大bug,开始疯狂加木属性,对水毫无想法。另外三个队围在一起厮杀,分数飞涨,我们队的程序在外围使用可怜的水属性发射镜像试图骗分。

随机种子助我们一臂之力,在两次连续的回合中,我们打到了一个队伍,分数瞬间来到40+。

在最后的决战阶段,我们严重怀疑其他的队伍的程序出现bug,在近身缠绕之后被我们的程序的镜像痛打(我们的木属性可是加满了的啊)。之后我们的分数就神奇的到达了90。

我们的程序熬到了最后,总分100,在一片惊呼声中拿到了第一。

北京队的三个团体赛选手也意外的收获了iPad。



今年NOI和以往一样欢乐。金、银牌分数线下降,大家都很开心。

各路神牛在常州参与了一场party。。。就是这样。




  评论这张
 
阅读(6063)| 评论(30)
推荐 转载

历史上的今天

评论

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

页脚

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