A blog about programming

0%

PKUWC 2018 && WC2018 游记

PKUWC 2018

day 0

报到日(话说北大营连胸牌都不发,就发了张时间安排的纸?)

day 1

上午考了数学,题目涉及很多方面,从小学数学到大学数学,从数论到几何,题型分选择题(30道)和证明题(4道),感觉两个小时的时间不太够,证明题都来不及想出证法,只能随便写点过程(数学还是菜啊……)

下午是第一场上机考试,赛制是实时评测+公开排名,排名的第二关键字是提交次数……第一题是一道树形DP题,正解应该是线段树合并,但我没有想到,就先写了40分暴力,再试图进行(常数)优化,想至少得50分,然而交了十次左右也没调出来,排名下跌了不少……最后只能放弃这题去做第二题了。第二题是个计数问题,我一开始没什么思路,写了个10分暴力,然后就去优化第一题了,等再回来做第二题时已经只剩一个小时出头了,发现m=k的二十分部分分很好写,是个简单的DP,很快拿到,但之后时间已经不多,来不及想其他情况了,就只得了30分。第三题是个不可做题,是斗地主判断地主能否春天,全场无人得分……(手动@jiry_2)

最终得分40+30+0=70,因提交次数排在100名左右。

day 2

上午是第二场上机考试。第一题是个状压DP题,比较简单。我先写了暴力,再写正解,一开始只得了90分,后来卡了卡常就过了,只用了一个多小时。第二题是个概率题,先写了简单的10分暴力,再写了30分的状压DP暴力,然后就不会做了,此时考试才过去一个半小时。第三题是个算期望的题,我连最简单的情况和暴力都不会,也不敢乱搞(提交次数会影响排名),就几乎无所事事了三个小时……

最终得分100+30+0=130,排名70名左右。

下午是面试,一个小时一轮,共三轮,面试官总是问一些莫名其妙的无聊甚至是重复的问题,让我不禁怀疑这个面试有没有实际作用。

day 3

上午是闭幕式,北大的老师讲解了六道题目,大家还合了影。中午是签约,我拿了张有很多很多条件的约,基本就是废纸一张。所有人都拿了一张“约”结束了北大营。

WC2018

day 0

领了胸牌和材料(包括一本讲义,印有讲课课件),这个学校全校都有wifi诶!(虽然宿舍没有……)晚上是开幕式,节目乏善可陈,CCF主席杜子德也没来,唯一有用的消息是今年wc要考交互题。(啊,还有我加入了wc的同学群,这也是非常重要的)

day 1

上午是lzz讲课,讲了两道ioi2017题+一个叫competitive analysis的东西+中美oi的差异。讲到后面competitive analysis的时候感觉已经睡倒一片了……毕竟是纯英文的幻灯片+夹杂不少英文的讲课,我并不知道这个东西有什么用……直到最后谈中美oi差异时才有精神过来。

下午是myy讲课。他一个湖(hu)南(lan)人,咋就去mit了呢?他主要讲了如何在TC上出题,他的出题经历及他出的题。故事还是挺有趣的,myy炫耀了他出题卡掉tourist和Petr的经历,但题目听不太懂。据说他出的那轮SRM的rank1yanQval也在现场,感觉非常厉害。最后他谈了谈在mit但经历并介绍了一下mit。

晚上是试机。并没有试机题,所以很快就回宿舍了。这里的键盘回车键好短,用着很怪,差评。

day 2

上午是jiry讲去年PA的题。首先他接受了来自去过pkuwc的同学们的嘘声(并没有,只是在群里吐槽了而已)。前几道题目还能勉强听懂,后面就听不懂了。最后两道题是分布式计算的题目,我总算是知道啥是分布式计算了……

下午是钟知闲讲NP-Hard问题的做法,讲了一堆多项式算法和非确定性算法,基本跟不上节奏,回去看课件吧。(不过好像也没几个人在认真听课)

晚上是营员交流,lca讲了卷积定理。他真的认为在ppt上摆那么多数学公式我们真的看的懂吗……不过他在讲课中提到的子集卷积,在最后的考试中有用到。除此以外,zgg介绍了交互题的解答方式。

day 3

上午是wys讲傅立叶变换。他认为傅立叶变换需要从物理的角度来解释,还举了几个例子。不过我们并不知道这些例子与傅立叶变换的关系,只记得他总是在放的一首歌(的前两句),通过听歌识曲功能得知那首歌叫《水木道》,一首清华人自己写的歌,他还因此获得了“电音之王”的称号,从此大家提到wys就不总是想到缓存优化和卡常数了……然后他推导了fft,没多少人在听,但一讲到如何优化fft,大家都精神起来了……不过他并没有告诉我们要用缓存优化,而是一些正常的优化方式,看来他改过自新了。(btw,今年wc的第三题那道交互题就是他出的,他确实改过自新了)

下午分两场。一场是immortalCO讲他的圆方树和动态动态规划,我感觉他经常讲圆方树这个东西,不过这次他主要讲的是一般图上的圆方树和树上的DP,没怎么提仙人掌。另一场是dyh讲博弈,并不能听懂,只知道后来杜教发现自己推错了浪费不少时间,最后好多张幻灯片没来及讲(我觉得他不说他推错了也没几个人能发现的了……)还有就是他居然穿一件短袖讲课……身体真好。

晚上是第二次试机。这次有题目了,两道noi2017原题+一道弱智级的交互题。我随便写了写代码就回宿舍了,反正也没有地方评测。结果宿舍停电了,只好回机房又呆了一个小时才回去。

day 4

上午是yjq讲图论算法。一开始讲的mst的算法,tarjan、kosaraju算法基本没人不会,但后来讲的东西我估计就没有人会了。

下午是xmk讲lzz剩下的四道ioi题+计算几何。可能是因为这是最后一次讲课的缘故,大家发言都比较积极,尤其是对一道初中几何题的时候……

晚上有两组营员交流。一组是包括了大名鼎鼎的wxh(我并不知道他为什么这么出名……)的三个人讲一道集训队互测的字符串题,另一组是张宇博讲了平面图上的算法。都没有怎么听懂,而且由于第二天要考试的缘故,体育馆里也稀稀拉拉的,不少人回去准备考试了,没有来听课。回到宿舍发现密码条在枕头下面……

day 5

考试日。第一题的暴力看起来挺好写,数据类型为0的也很简单,一共能拿44分。难道wc变简单了?我立刻写了这44分的程序,然后去做第三题。第三题的暴力似乎又能拿40分?赶紧写赶紧写。链的情况随机一下也能过?赶紧写赶紧写。这样就有60分了。然后看第二题。没看懂什么意思。写个暴力试试。小样例调了半天才调出来,结果大样例WA了。难道是题目理解错了?改改改。结果大样例TLE了。我决定放弃第二题,随便交个暴力,因为时间也不多了。中午吃饭时听说第二题题面出错了,但只通知了集训队员。卧槽?还有这种事情?主办方后来想了个解决方案,造两套数据,原题面的和正确题面的,然后取最大值,但很多事情已经无法挽回了。这应该是oi史上最大的出题事故吧(SkyDec说这锅我不背,应该广播来背,但您老能别总出计数题吗,pkuwc没出够吗?)。

下午出分数推迟了很久,因为要重造数据。最终得分28+0+70=98.T1暴力少了16分,当时很不解,后来想想好像确实写错了。在wc这种高难度的比赛中,每一分都很重要,因为这种简单错误丢掉分数是很不应该的。T3比预期多得了几分,挺高兴。但好像其他人总分至少都在100+,感觉自己滚Cu了。讲题没怎么听懂,只是觉得T2如果题意清楚50分暴力应该很好写,加上那50分就有望Ag甚至Au了,感觉有些失望。

晚上是文艺演出,十分有趣。我第一次了解到原来qq聊天的内容也能做为弹幕投射到屏幕上。许多同学唱了歌,其中有两首是oi改编歌曲,还有dyh和wys合唱水木道(其实只有dyh一人在唱233),还观看了集训队的滚榜情况,在高兴之余想到没进侯选队的集训队员就要就此退役,还是有一点点点伤感吧,不过更多的是获得了继续学习oi的动力。

day 6

上午参观了湖南省博物馆。人很多,时间却只有一个小时,不太够,所以没怎么认真看。不过文物看起来也确实不咋样,也不是很多,那个马王堆的女尸看起来也没什么特别的地方。

下午是闭幕式。果然得了三等奖,大概是三等奖的中等水平。总之wc结束了,该回家了,这次wc收获还是挺大的。