ZJOI一试酱油记

VictorWonder posted @ 2015年3月31日 18:04 in 总结 with tags 游记 , 1794 阅读
感(sang)人(xin)肺(bing)腑(kuang)的ZJOI终于又到了……下面是我的酱油记。
UPD0 : 这篇文章莫名其妙地消失了一次,这篇是重发的。幸好机智的我在出问题后马上就把全文复制了一遍233

Day 0
      今天一大早就出发了,因为拉着个箱子,感觉去学校食堂吃早饭的话比较拉仇恨,我提前就买好了丰和的虎皮蛋糕,没有吃饱。从候车开始我就在听歌,用的是新买的蓝牙耳机,耳机只有一个差评,各种不习惯。到了杭州坐公交车,以为要付两块钱,谁知只要付一块钱,我就帮老师把钱付了,然后,我还没有说,就看到老师拿了一张卡刷了一下……算了,就当攒人品好了。
      住的是全季酒店,据说这是据学军最近的酒店(雾,为什么我感觉还是十分遥远的样子),双人间满了,只能住大床房——不过没关系,老师回家住,也就是说最后还是剩下我一个人。去学军报道,结果是第一个,回来的时候碰上了jiry、dzy和另外两只不认识的野生大神,当时就吓尿了。下午在宾馆有点不舒服,什么事都不想干,然后就颓了两个小时的游戏,后来才知道lzw就住在我隔壁的隔壁,我们两个人再加上lzw的一个同学一起去吃饭了,去的时候碰上了策神,吃完饭又碰上了杜教和alpq。无数野生大神出没,ZJOI果然无比危险……
      晚上又颓了一会儿,然后就滚去做题了,调了好久没有调出来,最后和lzw一起讨论数学,在一个SB问题上纠结了很久,囧……另:竟然有人在门缝里塞了H广告,你确定这是正常酒店做的事?←无限orz看到了这些字的人
 
Day 1
      四点钟就醒了,五点多的时候实在是呆不下去就起床了。早上本来打算是早点去的(实际上我们仨是整个旅馆第二波吃饭的,且第一波只有一个人),单质lzw的那个同学zbt的狗牌丢了,我们找了好久,最后还是没有找到。去的时候前面的位置差不多都被占满了。
      本来以为,按照惯例(?)早上又是xyz讲课,结果竟然是绍一的jyk大神讲课,TC题目选讲,说是都是水题,我只能呵呵了。第一题是道傻逼题,YY一下就知道大致怎么搞了,刚刚看了一下课件,好像是某场SRM div1的T1,第二题也还可以,如果课件上的题面没有出错的话,应该还是可以想到正解的。从第三题开始就各种鬼畜了,基本都是SRM div1的T3,让我这种div1一道题都不会做的人情何以堪?感觉就矩阵求交(这题好像是某场div1的T2)和最小割的那两道题目还行,其他题目都是什么鬼QAQ
      下午先是jc讲课,讲的一样是TopCoder上的题目,不是SRM,是TCO(虽然不知道有什么不同)。没想到这次策神各种良心,讲的题目都听得懂,果然开学校的男人就是不一样(教练,我要上鏼工业大学!),虽然听起来都很简单的样子,但想到这些做法就已经需要CTSC级别的思维。第二节课是wys讲课,松爷硬生生地将VFK的30分钟给延长为两个小时,为我们深入浅出(雾)地讲述了仙人掌——没错,又是仙人掌,而且,还出现了鬼畜的动态仙人掌IV和EXT,竟然需要Top Cactus你怕不怕!话说,坐在xyz后面的那位同学,你真得不打算讲一下怎么打只有5k的Top Tree。还有那位多次被题目点名的同学,请你不要再讨论什么仙人掌上k短路、仙人掌路径最小字典序神马的行不行,我真的要感动得哭了TAT
      晚上我们一起花三个小时做了一套试卷,我坑了两个多小时就懒得坑了,幸好T3以前做过,是CF上的原题,我直接扒了过来(估计让我打晚上五个小时都不够),T2是数学题,我是个数学渣,就没做了,T1想了个暴力做法,结果谁知道我的想法有点问题,暴力分都没拿满,这果然是铁定滚粗的节奏么……另:orz碾压我们所有人的zly
 
Day 2
      早上两点钟的时候莫名其妙地醒了一次,后来睡到了五点半才起来,因为吃饭还是比较早,去占了好位置。
      早上是dyh讲课,讲的是自动机,杜教说,以前也有人讲过这东西(听说乔爷13年WC的时候讲的),不过讲的比较水(顿时就有了种不好的感觉)。其实刚开始介绍自动机概念的时候还是挺不错的,都听得懂,讲的四道题中也能听懂一些,到后来讲DFA最小化的时候就真的是听天书了,勉强听了点,开始讲题的时候我就打开了电脑继续调试程序了。最后听了NEERC的那道题,让自动机石头剪刀布,确实挺有趣,不过做法真的是太神了orz
      中午终于把决战的程序给调出来了,原来是维护权值的splay上少打了一个clean,简直要吐血了,坑我好几天。
      下午先是lxc讲课,听着听着就不知道在讲什么了,约大爷果然神,给跪了,然后就和大众一起弃疗了。之后是fsy(卧槽,突然发现我同桌的名字缩写也是这样)、crx和zxy(←高一金牌团)讲一些杂题,第一题还行,后面的就有点跟不上节奏了,只能中排膜拜了。
      晚上就是试机,分配到了大神云集的图书馆,结果我左边是金牌爷(zhw),右边也是金牌爷(zxy),简直不能活,整个考场内至少有五个金牌爷,除我之外各个都是大神,打代码发出的声音就跟下雨一样,吓尿了。另外,今天是愚人节(zxy的课件中出现了好几个欺骗大众感情的地方),没能在学校和同学一起过真是有点遗憾,话说,明明一直都是在三月份考的省选一试这次干嘛卡在这个时间段呢?难道是想说明这次考试就是个玩笑?
 
Day 3
      早上还是没有睡好……三点、四点、五点各醒一次,开始有点头痛,好在后来好多了。本来还想背几个模板的,后来就忘了,突然发现我连iSap的模板都没有背。
      讲一下试题吧:第一题大意:给定一棵开始时点权为0但有边权的十万结点的树(根据某条约大爷定理,这应该是水题?),支持某节点权值增加或减少,并且在修改之后回答:找到一个结点,使得该结点到所有结点vi的距离乘以vi的点权之和最小。开始的时候吓尿了,以为是动态虚树——昨天下午听课的时候我莫名其妙地想到了这个东西,然后有点后悔,早知道昨天晚上就问Claris怎么搞了。后来发现好像不对,因为结点的权值会改变,这样的话重新DP速度铁定会超时。然后觉得应该是树分治,但是想了十分钟左右都没有想出来(听说标算就是这个……),然后就开始想乱搞做法,这道题的题面上有个条件:每个点的度数不超过20,然后我就想到了爬山算法……因为在大神云集的图书馆,各种Debuff环绕,打了两三个小时才搞出来,最后半个小时一直在对拍随机数据。其实我的做法只要一条链两端加减权值就可以卡掉,我在考场上也试过了,大概要跑十几秒,很明显,6s是跑不出来的,但是懒得管了,本来是打算特判一下的,后来想想一条链的是可以特判了,万一是一条链,只是在两端的时候来了一个分岔,我这种做法还是能被卡掉,所以就懒得搞了,而且时间也没剩多少了,开始坑T2。
      第二题大意:给定一颗十个结点的树,有m条边,每条边边权是[0,1]之间的一个随机实数,求最小生成树最大边的期望。Note : 随机n个[0,1]之间的数,第k大的数的期望为$\frac{k}{n+1}$,这道题目给足了部分分,暴搜的话可以获得50分的分数,还有10分的特殊数据,m=n*(n-1)/2,我开始以为答案就是0.5,后来发现好像是错的,时间来不及了就没有继续想了。这道题类似的题目陈老师在WC的时候讲过,据说用状压就行了,问题是WC的时候根本没有听懂啊啊啊!
      第三题我连暴力都没有打,题意是这样的:给定一棵树(怎么又是树……),每个点有个字符,求所有不同的子串数目,对于结点数小于2000的序列,每次都DFS一遍,然后用hash判断一下就行了,结果我硬是没有想到,以为要枚举任意两个点,再求LCA,然后再找到序列,hash判一下……一看就很麻烦,然后就弃疗了。标算似乎是树上SA或者SAM,因为题目中有个叶子节点不超过20个的条件……好吧,据说很多人都看成结点度数不超过20了?orz看错题面仍然rank3的jiry。
     哎,就这样滚粗了……真是忧伤啊……
 
UPD1 : 去看了两位200+大神的总结,给跪了  @Stilwell  @JCVB
UPD2 : Claris表示这次省选除了T2需要点智商,其他都是基础题,给跪了。
UPD3 : 据说陈老师去给湖南送温暖了,我只想说,丧(gan)心(de)病(piao)狂(liang)。祝湖南大神们省选愉快……
UPD4 : 万一Stilwell和JCVB进国家队了,我们标准分该怎么算……愿高二大神全都进国家队……
UPD5 : 可以去这里看成绩。我侥幸拿了130分,感觉各种虚,我的智商和大神们差一大截,还要继续努力啊!
 
附:官方题解链接,ORZ 陈老师 : http://wjmzbmr.com/archives/zjoi-2015-day-1题解/
Johnson Yip 说:
2015年3月31日 20:58

http://victorwonder.is-programmer.com/posts/85470.html
So, 解释一下这篇文章莫名其妙地消失了一次?
再次膜拜Victor Wonder ZJOI虐场。

Avatar_small
VictorWonder 说:
2015年3月31日 21:49

@Johnson Yip: TAT就要滚大粗了,就知道瞎胡说……

Johnson Yip 说:
2015年4月01日 21:14

后天你就是大神了。
坐等Victor Wonder虐场。

Avatar_small
VictorWonder 说:
2015年4月03日 10:52

@Johnson Yip: 我就呵呵了……

Avatar_small
VictorWonder 说:
2015年4月04日 07:33

@Johnson Yip: 哪有……和大神们比我差太多了……


登录 *


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