CTSC&&APIO酱油记

VictorWonder posted @ 2015年5月02日 20:59 in 总结 with tags 游记 日常向 , 1418 阅读
又要开始强行酱油模式了,赶紧水一发来骗点点击。
因为习惯了,所以打了两个&,感觉这样好像更符合我这个程序猿的身份?
北京真得好干燥,很容易口渴,另外,我已经深深地体会到什么叫做静电现象。
酱油记越写越长,都快成为流水账了……

Day -1
      因为明天报道外加试机,所以特地提前了一天到。早上九点钟的火车,五点半多点就起床了,昨天晚上睡得不是很好,可能是因为比赛Debuff?再加上可恶的蚊子……好在今天精力还行。
      今天其实没什么好说的,就是坐火车,可惜我们这边坐飞机不方便,不然就坐飞机了,票价差不多,而且速度快。虽然找到了插座,但是在火车上还是没有什么好玩的,信号好的时候看看小说,不好的时候就看看代码想想题什么的。本来打算看《具体数学》的,结果还是小说战胜了具数……
      到了北京之后有人接,是柯老师的同学,在北京工作,看上去有点老,但身子骨很硬朗。然后坐地铁到了人大边上。地铁上有一个大伯让我映像非常深刻,主要是这大伯侧面看上去有点神似我的初中语文老师,手里还拿着一本薄薄的书,开始我以为是文学类的作品,后来因为实在闲,想方设法看到了书名《狭义与广义相对论浅说》,霎时间就吓尿了。
      今天晚上住的是一家小旅馆,是张杰逸学长帮忙安排的,房间看起来相对小一点,但还是挺不错的。晚饭是在旁边一家叫做鸭王的饭店吃得,感觉烤鸭的味道也就这样。点了挺多的菜,最后四个人还是没有解决掉多少,我差不多吃撑了,看看时间也不早了,就提前退了,然而,直到我现在写这些东西为止,柯老师都还没有回来,不会还在那里拼酒吧?
 
Day 0
      横穿了人民大学,终于到了地方。刚到酒店门口就碰上了lzw,然后一起去吃了饭,吃的是西点,花了五十左右。本来说是三人房的,所以打算和lzw、zly一起住,结果却表示所有人都已经都安排好了,我竟然要和绍一的三位大神一起住,而且是四人大套房,喂喂,说好的二人间和三人间呢!
      早上报道之后就出去玩了,坐地铁去了西单。zly的建议我们一起去看大悦城的蜡笔小新动漫展,但是好像没有的样子?然后就去天安门了。明明说是一公里远,但我们走得腿都酸了才走到,因为时间没有剩下多少,就在金水桥前面拍了几张照。本来想要去看人民英雄纪念碑的,但是zly说要去王府井买纪念品,如果去看人民英雄纪念碑的话,回去后午饭就没得吃了(事实证明就算我们不去看,回去后午饭照样没得吃)。走路去了王府井,发现物价真高。在小吃街,一串羊肉串都要卖10元,然后去了王府井工艺品街,物价还是很贵,考虑到如果给全班同学都买纪念品,估计身上的钱花完了都不够,就只给同桌买了一支铁质的“兰”书签(虽然感觉这东西没有丝毫北京的特色)。回来后已经十二点半多了,到了人大,好不容易找到食堂就一点多了,因为来得太迟,自助餐的东西都已经没剩多少了,我们干脆去了校内的西餐厅,吃了奢侈的一餐,花了身上差不多一半的钱,这物价……
      在酒店休息了一个多小时之后就去试机了,走了很多路,脚很酸。走到之后却发现不能进入机房,机智的我们跟着湖南湖北和学军的大神们走,终于通过正确的路径进入了机房。回忆了好一会儿终于回忆起了Linux下的编译方式和对拍写法,然后码了个A+B和NTT(突然发现,NTT码多后,正常的FFT都快不会了),之后打了个LCT,好久没有打LCT了,出现了几个傻逼错误,调完后发现lzw和zly还在搞,就顺手打了个多项式逆元。键盘好不爽啊,和正常的键盘不一样,退格键的长度特别短,"\"键竟然在退格键的左边这个位置,然后回车键占了"\"的位置,好在打"\"和"|"的次数不是很多。最恶心的是Delete键,竟然在上键的正上方一点点的位置,每次都会按错Insert键或者截屏键,早知道就自带键盘了QAQ
      搞完之后就五点多了,回去的路上zly和lzw执意要跑步,我本来是打算看他们跑的,后来想想还是加入了他们,可是他们俩一点都不体谅我这个胖子,跑得特别快……去吃饭已经五点半多的,虽然就只迟了一点点,吃的东西就没剩下多少了,而且没有饮料,差评!
      晚上开始的时候没有状态,乱七八糟地不知道在做什么,本来想看暴走大事件的,结果网速那个慢,只能就此作罢。后来想起来CC的May Challange好像已经开始了,结果发现May Challange竟然推迟了,从8号开始,难道是因为CC知道最近举行CTSC?之后继续看链式反应的题解,终于看懂了,原来$x'(t)=\frac{1}{2}a(t)x^2(t)+1$是这么一回事:对生成函数求导等于将原序列往左移一位,元序列的$x^0$的系数为0,但是现在的系数变成1了,然后+1前面的这一坨是算出$x^0$项的系数是0,所以需要+1,突然发现自己好傻逼。之后的微积分仔细想想反而挺简单的了,r的选择挺巧妙但也是挺显然的。然后就开始看模板(背模板实在是来不及了),顺便问了lzw一些很傻逼但我还不会的问题,差不多就可以睡觉了。
 
Day 1
      今天就要考试,感觉什么都没有准备好的样子。于是,早起一遍后缀数组,不多喝水,不勤洗手……咦,不对,这场面怎么这么熟悉,我不会就要滚大粗了吧!
      一语成谶,打了一早上的酱油,果然滚粗了……第一题开头“小强和B君是好朋友”,什么鬼,先随手打了个20分暴力,小数据过了,大数据跑了好几秒才跑出来,结果答案还不对,不是精度的问题,然后检查了好几遍,也不知道是什么地方出错了。接着打了个树形的做法,调了好久才调出来,不过估计这20分还是能拿的。另外,还有人发现内存限制是233MB吗?第二题感觉标算肯定是可持久化Treap套上点什么,当然,如果有别的可持久化平衡树的话也可以做(原谅我的孤陋寡闻)。只要想出来怎么快速查询,这道题就可以做了,但是想了好久没有想出来,最后无奈打了10分暴力,因为没有东西可以对拍,再加上时间比较紧,只是肉眼看出了几个错误,估计这10分会出问题……根据同房间的绍一大神打探来的消息,T2好像有一大批人AC,听说用了什么可持久化4维K-D Tree?这让我们这种弱渣怎么活……最后,2G的内存又是什么鬼。第三题是令人无语的提答。不送分的提答,能叫提答吗?搞了好久只拿了10分,第一个点1分,第四个点9分,第四个点用了13步,就差一步就可以多拿一分了,但是在考场Debuff的作用下,还是没有想出来TAT
      吃完饭之后去买了一支棒冰,终于见到生产日期是今年的巧乐兹了,真是感人肺腑。
      成绩出来了,是前所未有的惨败,T1和T2都爆零了,就T3拿了10分。T2倒是还情有可原,只是T1挂的不应该,暴力都可以做的题,虽然我当初也想过打SPFA什么的,但最后还是没胆,觉得CTSC的题目不可能这么简单。以前经常说就要滚粗了,最后的成绩其实都还看得过去,这一次真的是要滚了,有种淡淡的忧伤,整个四月份都不知道在做一些什么乱七八糟的事情,状态一直都不太好,如果再这样下去,估计真得没有任何希望了吧,我的OI之路……
      晚上虽然想要做题,但开始的时候看了一些题,感觉都挺麻烦的,最后下决心要坑掉APIO2013那道Robots,照着PoPoQQQ的程序打的,还是没有调出来。
 
Day 2
      早上起来稍稍改了一下,终于把Robots这题给过掉了。然后开始写道路费用,吃完饭后改了一下就AC了,紧接着就去听答辩了。
      答辩去得挺早的,挑了稍前面的几个位置,开始以为每个人都要讲20分钟,估计讲到下午都讲不完,王宏教授就说每个人只有8分钟的时间+4分钟的提问,时间挺紧的,然而,事实证明人类的潜力是很大的,最后竟然在12点前全都讲完了。感觉今年的答辩其实没大多意思,主要是因为每个人答辩的时间都比较短,讲的很多东西都听过大概,论文里面介绍的一些比较新颖的东西讲的不是很多,看来只能以后慢慢啃论文了。不过还是讲一下对于答辩的感觉吧。
      第一个讲的是lyy,其实讲的就是《诸神眷顾的幻想乡》的做法,ZJOI Day1之后,一直比较颓废,题目一道都还没有AC,开始以为这道题很简单,听完之后发现自己YY的做法复杂度好像很不对。第二个是Stilwell讲启发式思想,斯坦纳树近似解法听着还行,大致能听懂一些,对于他说的A*算法及其拓展,我还是蛮期待的,可惜答辩的时候没有仔细讲。Sone大爷讲的覆盖也让人大开眼界,挺有意思的,但感觉这东西绕来绕去还是绕不开通常的字符串算法。接着是keavil.Zhang的后缀自动机,没仔细听,毕竟后缀自动机打过几遍,差不多也会一些,主要还是一些定义上的东西不怎么懂,这么点时间也搞不大清楚。而且,zty被坑得挺惨的样子,先是ljcc(我感觉可能是他们事先商量好的)问他讲的东西和lyy讲的有什么不同,后来又有一个老师(我不大清楚其身份,WC的时候也见过,应该是叉院的大神,但都当老师好了)问他讲的和陈老师几年前讲的有什么区别。在JCVB还没有上去讲的时候,我作死去拿了一本论文集,谁叫lzw和zly都不争气呢,只能自己当第一个吃螃蟹的人了。在我看来,JCVB讲的应该是最没有意思的了,感觉和营员交流时候讲的没有多大区别,而且,我上个星期一直在坑这些东西,有很大一部分都已经搞明白了。
      之后是ljcc讲命题报告,也没有仔细听,只是觉得最后的多维FFT挺有趣的,有空得学一下(其实上次问过VFK,VFK扔给我一个Wiki的链接,但我英语太渣,实在是懒得看)。xllend3讲的东西我兴趣也不是很大,分块这东西历年都有人讲,我也做过一些题,他说的大致都听说过。最主要的是,分块这东西的复杂度不好把握,如果不能精确的计算出最合适的分块大小,很容易出问题,而我在这些方面恰好是很欠缺的。wangyisong1996讲的仙人掌就更没有听了,省选的时候都讲过了,虽然当时也没有怎么在听。仙人掌这东西最近确实挺火的,但我觉得距离其彻底普及开来还有一段时日,VFK在最后提的那个问题就已经反映了这一切,大家遇到这类题目都是打暴力就跑。Delayyy讲了图的匹配,这也算是老生常谈了,去年的WC上,kzf和hza都已经讲过了,看了论文,讲得是挺详细的,但觉得一般情况下,这种东西考到的概率不是很大(主要是一般图匹配问题),二分图匹配大家又都会。csy讲了物理题,基尔霍夫定理和$Y-\Delta$等效代换竟然属于简单的物理基础?吓傻了,我这样的物理渣还是早点滚吧。
      saffah的命题报告挺有趣的,那场镜像我也参加过,不过好像由于作业没有做完,就不坑了,因为根本没有看到“传统题”这个条件,以为第10个点是最不可做的,之后才知道原来这是最水的一个点。张恒捷(我实在不知道他的网名是什么)讲的DP优化有点意思,其实,斜率优化什么的就是最简单的函数拟合吧?觉得他的这篇应该是最需要看的,毕竟我DP方面这么弱。xudyh我不作评价,杜教这么神,我反正是听不懂的,我暂时还是远离群论吧。突然发现约大爷的网名不会打(好吧,是Ruchiose),暂时就先这样吧,他讲的东西也是ZJOI Day1讲过的东西,话说,如果选手对于这些东西没有研究,您确定有人能在一个半小时到两个小时之间做出您的题吗?最后则是VFleaKing讲的集合幂级数,虽然没有听懂,但感觉好厉害的样子。想到这是VFK自己YY出来的,顿时觉得自己无比渺小,数学这方面的东西其实最需要厚积薄发,我看来是没多大可能性赶上了。最后,但愿今年ZJOI Day2不会是VFK出题,那样我不得不抽时间学一下这东西了……
     下午去了国家博物馆,时间太短了,所以没看多少。本来的预计是2点钟到那边,然后参观1小时40分钟,实际上是,我们到那边已经3点了,我、zly和lzw先是去看了近现代绘画艺术展(似乎是这个名字的样子),那个展览正好位于复兴之路展区,所以里面都是革命相关的题材,不过总算看到《开国大典》的真品了(据说这也是复制品?下面的介绍挺长的,没看仔细)。接着去了二楼,二楼的走廊上是一些宋代石雕,绕过去之后是一块暂时不展览的区域,就去了另外一边的建筑设计,里面都是照片,经发现,又一大部分都是国博的照片,唯一的看点就是摆着的国博建筑模型,所以我们就出来了,去了三楼。三楼走廊上也有一些文物,但没仔细看,我是想去看瓷器的,奈何zly非要去看友好往来区(展览区的名字也忘记了),里面都是建国以来,外国友人赠送的物品,其实还是挺有看头的。很多东西都不怎么会欣赏,尤其是非洲那边国家的赠品,主要还是看一些绘画,印象比较深刻的是欧洲某国(好像是法国?)送的水粉风景画三幅,还有非洲某国送的蝴蝶象棋,是用蝴蝶翅膀制成的国际象棋,很美丽。很多都是金属制品和玻璃制品,大多数金属制品看起来都很精致,尤其是茶具、碗什么的,看上去很光滑,闪闪发光的。还没有看完,时间就差不多了,走的时候看到大厅中央有一架大船的模型,这里展出的船的模型挺多的,但都是比较小的金属制品,这个大船的模型特别大,随手拍了几张照。到了大厅之后才知道,延迟20分钟走,于是去了地下室,地下室最外面是原始人类使用的物品,里面没有进去看,估计也差不多,感觉没多大意思就出来了,去三楼买了纪念明信片,有国博的纪念章,而且挺便宜的(别的都买不起啊,大多数纪念品都是三位数的,甚至还有五位数的),买了两份,一份自己收藏,一份送同学。回到人大之后正好是饭点,吃完饭后去人大的报刊亭也买了明信片,人大手绘明信片(当然不是真得手绘的,正面是人大同学手绘的人大景物),挺精致的,也买了两套,打算过几天寄回去。
      晚上本来打算按照lyy的论文实现一下扩展SAM的,结果发现lyy的论文太过复杂,然后就远程咨询了一下Claris,用他的方法过掉了陈老师那题(当然,构建SAM的部分是照着模板打的),就是对于Trie上每个结点记录将当前结点插入到SAM后的last是哪个结点,然后每次要遍历Trie上一个新的孩子结点的时候,就将last重置一下,不知道是不是和lyy论文里的做法一样。还看了一下JCVB的论文,感觉比白天讲的内容要充实很多,可是还是没有$O((n\log n)^{\frac{3}{2}})$求复合逆的做法,差评!虽然我是“感兴趣的读者”,可我真的是懒得看英文论文啊……之后和同学聊了会儿天(主要在讨论目前已有的明信片的归属问题),估摸着时间差不多了,洗了个澡,就睡了。
 
Day 3
      今天早上起床的时候还在幻想今天能够翻盘,现在看来,对于我这样的人来说,这只是奢望而已。一试是最容易拿分的,我却丢了这么多分,今天二试就更别说了,标准的CTSC难度,题目的难度都很大,我就更不要说拿多少分了。
     T1似乎是道图论题?看起来挺奇怪的,考场上本来是没有打算坑的,最后发现10分暴搜就可以了, 如果没有出太大偏差,这10分应该还是能拿到的,但是感觉我的常数略大,可能会被卡。T2是我觉得挺可做的一道题,所以在这道题上坑了两三个小时,但最后还是只打出了5分的暴力,部分分给的是挺多的,我也想了很多做法,包括分块、离线、树套树什么的,却都没有任何结果。这道题的插点和删点很明显是需要用数据结构来维护的,一般来说,平衡树就差不多了,线段树也是可以的。查询就令人讨厌了。如果没有插点和删点,这就是一道简单的贪心,$O(n^2)$是可过的,我也想到过$O(n\sqrt{n})$的做法,但仅仅只是针对查询而言,对这道题并没有什么作用。T3仍然是一道提答,叫做CTEX,其实和CTEX没有任何关系,大意就是给出一个01自动机,把边和结点都告诉你,而且,有一些结点是输出结点,但是每个输出结点会输出什么字符不告诉你,另外,每条边上可以接受的字符也不告诉你,然后,告诉你自动机能够接收怎样的字符串,并且会输出什么内容(字符串在自动机上每到达一个输出结点就会输出相应的内容),选手需要根据这些把自动机补全。而且,每条边和每个点对应的不同状态都有一定的概率,比如说,一个结点输出0的概率是P0,输出1的概率是P1,不是输出结点的概率是P2,最后要求,补全的自动机概率需要最大(这里的概率使用整数表示,整数越小表示概率越大,也就是说,要求最后选出来的整数和尽可能小)。我开始并没有坑这题,后来发现前五个点每个结点输出什么都是已经说明了的,但是剩下的时间已经不多了,我也没有什么好的想法,只是草草地把第一个点给搞了一下,也不知道有没有分,这次的提答特别坑,spj竟然连分数都不告诉。
      成绩不出所料,只有15分,感觉反而还行,毕竟大多数人估计都是这个分数左右,Day 1真是考得太差了……
      当了一下午的看客,这种感觉真不好,真的是不想再经历一遍了。
 
Day 4
      今天是APIO报道日,一天都很闲,所以打算出去玩。
      早上花了点时间把ydc的题面给做了,第3个点是搜索,不怎么会打,就参考了VFK的程序。报道之后去了一趟人大,把几张明信片都给寄了,之后就去吃饭了。在寝室呆到下午两点,出发去了北大。恰好北大下午2:00~5:00允许游客参观。北大的校区挺幽静的,感觉就像是一些山中的景点。因为赶时间,所以只是走马观花地看了一遍,希望以后还有机会来这儿。大概三点半左右,终于在一个好心的北大学长的指引下,找到了邮局,买了明信片寄了回去。之后走了好长一段路,终于到了清华,结果因为不是周末,清华不让进。本来我打算去旁边的颐和园逛一逛,但是lzw说走了这么多路,挺辛苦的,就打道回府了。
      晚上没有去人大吃饭,因为lzw说这是最后一次可以吃大餐的机会了,然后我们就去吃了必胜客(囧),吃完饭时间就差不多了,晚上回来后,看了一下训练赛的题目什么的,颓了会儿就睡了。
 
Day 5
      早上终于耐着性子讲训练赛的9道题都看完了,顺便将C题给水掉了,英文看起来好不爽,幸亏APIO比赛是有中文翻译的。
      第一个讲课的是钟皓曦,他的普通话似乎是我见过的几个大神中比较标准的一个了。讲的是概率,挺有意思的,而且难度似乎都不是很高,除了最后讲的蒲丰投针问题,其他的都差不多听懂了,另外,钟老师还动用了比传话筒更丧心病狂的手段,拿着名单点名,在此,我非常感谢自己的父母没有给自己取4个字的名字。第二个讲的我不认识,讲的是hash函数和A*算法,没多大意思,而且讲的也不太好,所以就没有怎么听,听课的时候zky就坐在我正前方,看他和旁边的一个同学一起玩一个游戏(似乎是ubuntu自带的?),看上去很有趣,我琢磨了一会儿,大致搞懂了玩法,感觉这游戏拿来出提答似乎挺不错的样子。
      中午吃完饭之后就直接去了机房,但是由于NOI Linux的Firefox的版本太低,竟然看不了题,后来下了个最新版才看到题,把D题给水过去了,因为一个SB错误,肉眼看了好久,然后又是讲课,讲了面向对象的一些特点,皮卡丘的例子挺有趣的,大致听懂了,之后似乎就一直在打广告,而且话筒不太好,声音一下大一下小,所以就没有仔细听了。
      晚上和lzw一起做了CodeChef May Challange的题目,然后颓废了会儿就睡了。
 
Day 6
      早上还是很早起来,吃完饭又做了一会儿May Challange的D题,很快就水掉了,之后做了一下E题,感觉可能是卡常数,暂时还不知道更好的做法。然后就去考试了。
     APIO的T1是道位运算的题目,感觉是DP,中途想了个转移方程,结果怎么也过不了,后来才发现我的转移方程有一个很大的漏洞。T2是最短路,问题是不知道怎么优化建图,最后就拿了五十多分。T3的题目不好分类,先用线段树把K=1的数据都给做掉了,之后K=2的数据就怎么也过不掉了,后来才知道原来是不需要建立桥的情况,返回值是0,但是我的返回值是无穷大(因为要求最小值)。最后两位数滚粗了,但愿还有铜牌吧。
     下午讲题的时候发现自己特别傻,T2别人都用Dijkstra+堆优化过了,我当初怎么就没有好好想怎么卡常数呢?T3也是SB了,明明都已经打出了三分套三分,结果就差一种情况没考虑到,这么多分就都没了,否则至少还有三十分可以拿,而且,稍卡一下常数的话,AC也不是不可能。
      今天的晚饭是最差的,坐的位置没有也就算了,连米饭都没有,草草地吃了一些,也不觉得饿,就过去准备听课了。讲课的是冯齐纬(应该是这么写的吧?),开始的时候讲了V图,因为有图片,而且每一点都详细地介绍了,还在黑板上画图(感觉fqw老师真得好认真),所以听得蛮有意思的(其实主要是感觉他讲话的声音听起来比较舒服),之后讲了kd Tree,不过和V图一样,都只是介绍了大致的构造流程,感觉如果真得要坑的话,得花一些时间,然后扯了一些光线追踪的东西,似乎听高大上的(但是我没认真听),之后再扯了一下VP树,就结束了。时间还有十分钟多余,fqw老师又讲了一些有(gui)趣(chu)的东西,是三角形不等式在求哈密顿路近似解上的一个应用,没怎么搞懂最后的证明(主要是急着准备回来)。最后,fqw老师画的图真不错,赞一个。
 
Day 7
      今天是最后一天,早上是两个人大的ACM选手讲课,第一个讲的挺好的,差不多都听得懂,只不过这些题目对思维的要求比较大。第二个讲的就有些无所谓了,只讲了五六道题,除了第一题还行,后面的都不知道在讲些什么,我就没有怎么听了。下午第一个讲的是昨天晚上fqw讲的光线追踪,当然,光线追踪只是其中的一小部分,他讲了真实图像的渲染技术,开始的时候还仔细听,后来,由于图片根本看不清楚,代码因为背景的缘故,也看不清楚,所以就懒得听了。第二个讲的是pty,讲了一些google和微软的面试题,大多数都在于用极小的内存实现一些问题,挺考验智商的,也确实挺有趣。
      晚上和柯老师、张杰逸学长以及柯老师的同学一起去三楼吃了饭,之前一直是在这儿吃自助餐,感觉真得是不怎么样,没想到,饭菜竟然挺好的,可惜就是贵了点。lzw跟我说,那边7:30才让进,我就慢慢吃,然后zly告诉我,七点钟的时候就已经开始了,我就拼命跑过去,还是略过了我的名字,果然只有铜牌,哎……
 
Day 8
      一大早就出发了,结果火车因为线路问题晚点了一个小时。快到站了才想起来没有给机房那几位买纪念品,幸亏上次去北大买了书签,虽然只有五张,到时候谁先见到就先给谁吧。
 
总结
      这次CTSC和APIO,总的来说是比较失败的,出现了各种各样的问题,但是,在这两次比赛的过程中,我发现了自己的一些缺点和漏洞,现在补救还来得及,而且,在讲课,尤其是APIO讲课的过程中,学到了很多新的知识,有所收获,这次CTSC和APIO也算是物有所值了。

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter