2019年的冬季,蒟蒻的PKUWC游记(12.20~12.23)

前言

这次我能够和(XZY)神仙一起前往(PKUWC),是作为一个非正式营员的身份。

什么是非正式营员呢?就是没有资格参与面试,也没有资格参与颁奖的体验者。

也就是说,我这次前往(PKUWC),仅仅是为了体验,感受一下(PKUWC)的氛围而已。

毕竟我(CSP)分数不太高,实在是无比弱小,大概只能给(XZY)这种神仙当陪衬吧。

(Dec 20th)

正式出发

今天,是正式出发的日子。

虽说是星期五,可并没有去学校晨跑。难得睡到了(7)点,起来匆匆吃完了早饭(一个手抓饼),就出发去火车站了。

到了火车站,已是(7)(40)左右。去取票的时候无意间看见了(XZY)神仙,然后等小叶老师来了之后便一起上了高铁。

在高铁上的时光很是漫长,也的确漫长(从上午(8)点多到下午(3)点半左右,共(7.5)个小时)。

而我在高铁上干了些什么呢?

因为(XZY)神仙开了热点,所以就有了网。然后我就写了两道题:【洛谷5644】[PKUWC2018] 猎人杀【洛谷5643】[PKUWC2018] 随机游走,且还有一道题没调出来。

结果由于高铁上没找到插座充电,我的电脑又不像(XZY)神仙的电脑那般经用,所以很快就没电了。

没电之后,我就头靠在墙上开始睡觉......迷迷糊糊的,好几次差点睡着,结果每次都突然惊醒过来。

于是乎,宝贵的时间就在这般无聊之中荒废掉了。

最终,在我急切的盼望中,北京,终于到了。

去北大报到

到了北京之后,首先坐了(20)多分钟的地铁,去了宾馆。宾馆很小,甚至有些地方还在装修,(XZY)神仙说这是个适宜拍鬼片的地方

安顿下来之后,本来小叶老师说让我们在房间里自己做自己的事情,结果过了一会儿她过来说要去北大报到。

因此,我们又坐上了地铁,且又是(20)多分钟,然后便到了北大。

北大很大。北京似乎前几天刚下过雪,因为在北大校园中,随处可见一捧残雪。

残雪,已经略显污浊的洁白,勾勒出北京冬日的那一丝清冷,引逗出我心中的那一抹冷意,以及几分茫然。

风,正寂寂地吹,心,却已颤颤巍巍。

此时已经天黑了,黑夜漫步在北大校园,似乎给人以一种极为特殊的感受。

然而,北大校园毕竟太大了,大得我们在里面走得晕头转向。

小叶老师找了几个北大的学生问路,又走了许多弯路,最终才好不容易带我们到达了目的地——理科(1)号楼。

据说是在(1117)号房间报到,然而,我们在里面转悠了半天,找到了(1116)(1118),却愣是找不到(1117)号房间在何处。

后来我们找到个北大的老师,让我们改去(1235)机房门口报到。

接下来的一切就很顺利了,在名单上签了个字,然后就发了营员证,以及两张饭卡,分别有(50)元和(100)元。

然后我们原路返回,走出了北大的校园。

夜,迷茫

晚上我们找了一家港式餐厅,饱餐了一顿。不得不说,还真的挺美味的。

然后便回了宾馆,在楼下偶遇(bzt),听说他们晚上吃烤鸭......

回房间后开始写题,感觉今天晚上效率不太高,就写了一题:【洛谷5492】[PKUWC2018] 随机算法

不过,后来又去稍微复习了一下状压(DP)和多项式的一些内容。

如此直至深夜,心中已经满是迷茫。在这样一个夜晚,我甚至有些不知所措,不知路在何方。

躺在床上,咳嗽咳得辗转反侧,突然感觉自己似乎有点闪指导的风范。

(Dec 21st)

早起,吃饭

早上(XZY)的闹钟是(6:45)响的,然后我就躺在床上赖到了快(7)点才起来。

刚起来还是有点迷迷糊糊的,刷完牙后用冷水洗了下脸,顿时感到清醒了许多。

早饭是在宾馆的地下一层解决的(发现电梯里屏幕上显示出的(B)非常诡异)。

早饭的内容还是挺丰富的,有一样很神奇的菜,似乎叫做炸鸡蛋,具体地,就是把鸡蛋炸了一下......

吃早饭时又看到(bzt)(lhc)巨佬,他们好像是要去清华的。

一不小心菜拿多了点,结果在那里硬吃,好不容易才吃完,都快要撑死了。

这时才(7:40),说要(8:10)左右出发,于是又跟着(XZY)回了房间。

开营仪式

早上依旧是坐地铁,抵达了北大。

由于昨天探路的经历,今天找到举行开营仪式的双创中心就省力多了。

开营仪式(9)点开始,其内容大多围绕着对北大与信息学有关的一些相关介绍,期间甚至还提到了一下最近社会课上刚好学过的四次工业革命

简单而言,这个开营仪式就是让我们明白了,北大的信息学很厉害。

在北大里瞎逛

开营仪式结束得很早,才(9:40)

于是,我和(XZY)就跟着小叶老师在北大校园里瞎逛了一圈。

我们一路从双创中心一直逛到了北大的西门。路上遇到几个雪人,其中有一个雪人竟是用一枝玫瑰花当手臂的......

然后我们在北大西门门口拍了张照。在北大拍照,还是很有纪念意义的吧。

接着,我们找了一家咖啡店坐了坐,我点了一杯盆栽奶茶,名字很新奇,从没听过。拿上来后,就是一小杯奶茶,上面铺了一层奶油,奶油上插着一小片草叶。样子还不错,味道也还行。

由于时间尚早,小叶老师又看我和(XZY)坐着很无聊,就把她的笔记本电脑拿出来让我们翻翻题目,准备下午的上机测试。

(XZY)翻出了一道题:【洛谷5794】[THUSC2015] 解密运算,然后我们就看着研究了起来。

这道题目还是比较有趣的,我在草稿纸上瞎画了半天,结果突然间灵感涌发,居然神奇地把这道题口胡了出来。

然后我们就去吃饭了。

本以为华茂、二中的食堂已经很大了,到了北大,才知道食堂可以有多么豪华。

首先,在北大,并非只有一个食堂,而是有好几个的,而我们吃饭的地方叫做农园。

食堂里真可谓是琳琅满目,有着许许多多的窗口,每个窗口风格各异,但看起来都挺好吃的,让我这个选择纠结症真是无从选择。

最后,跟着(XZY)神仙一起找到了盖浇饭的窗口。我点了一盘茄子和蒜苗的盖浇饭(吃素攒(RP)?),后来没吃饱,又去另一个窗口点了一盘炸薯条。

吃饭时顺便完善了一下前面咖啡店里那道题的想法,发现原先的想法有点复杂,便加以简化,发现简化完之后超级简洁。

吃完饭,我们便径直朝着机房而去了。

上机测试

看了看名单,发现我的座位号是(4)号,莫名感觉这个数字不太吉利,像是要死(呸呸)?

坐下没多久,比赛就开始了。

开局看(T1),感觉不太可做,便先写了个暴力,然后花了一个多小时试图找规律,结果以失败告终。

同时发现不知为什么我电脑上的(C++)不能调试,有点小郁闷,感觉(4)真是个倒霉的数字。

决定暂且弃疗,先把(21)分的暴力交掉了,然后就去看下两题。

(T2)一眼看上去想到先枚举最终合并成的集合个数,然后枚举一对(min)(max),并用组合数大力计算它们能够产生贡献的概率。

自以为想到了(O(n^3))的做法,还有些小激动,结果又是调了快一个小时,竟是死活过不去。

完了完了,心中越急,脑子越糊,一匆忙更加写不动了。

此时(T2)还没有分,结果又是弃疗,直奔(T3)而去。

(T3)看完题面,显然莫比乌斯反演+数据结构乱搞啊!

想到昨天晚上睡前本来看到一道莫比乌斯反演题,结果为了复习多项式,就没去做。现在回想起来,真是血亏!

由于太久没写过反演题了,结果有点生疏,再加上此时心情很紧张,一不小心就把式子推偏掉去了,完全想到了错误的方向上。

结果依然花了近两个小时,最后手造出一组样例把我偏掉的式子给(Hack)掉了,于是弃疗。

这么一搞下来,三题都弃疗了,还是只有(T1)(21)分暴力。

怎么办?鼓起勇气,厚起脸皮,开始写暴力分吧!

于是手速写完了(T2)特判(l=r=1)(l=r=n-1)(9)分以及(T3)所谓(nle 100)(6)分(本来想写(O(n^2))的,结果挂了,便只有(O(n^3))了)。

一看时间只有半个小时了,顿时又吓懵了一分钟......

接下来就是所谓抉择了,是想办法去推一推(T1)很丰厚的部分分,还是写一写(T2)单薄的(9)分暴力,还是去想一想(T3)(O(n^2))做法再多骗点分?

权衡之下,觉得(T1)(T3)的分数都有点悬,还是(T2)(DFS)暴力可靠一点,于是下定决心开始写暴力。

将近半个小时后.......

(T2)所谓可靠的(DFS),居然还没有调出来......

怎么办?心态爆炸,彻底凉凉。

估分(21+9+6=36)分?这说出来都不太好意思,毕竟连最低档的暴力分都没拿满,乐观估计全场倒数第一......

更何况,一走出考场,首先听到一群人说切了(T1),甚至还有一个人感慨这是他第一次在考场上切了题。

用闪指导的话来说,我真的是当场去世......再联想到(4)这个不吉利的座位号,突然有一种信教的冲动。

与法老吃晚饭

在考场门口等了一会儿,小叶老师便过来接我们了。同时我们也看到了法老!

法老带着我们去吃饭。

与中午不同,这次我找到一个名叫“清真·美食”的窗口,并点了一碗牛肉拉面和一串羊肉串。羊肉串看起来很好吃的样子,结果咬下去一半是肥肉,真是应了那句老话,人倒霉起来,喝水都会塞牙缝。

然后我去倒菜的时候又被食堂阿姨拦了下来,告诉我清真的盘子要放到单独的地方去。

我一开始很是疑惑,后来想了想,大概是因为清真对猪油等食物有禁忌,放一起可能会有污染吧。

吃完饭后顺便向法老咨询了一下(T3),经过法老的简单指导,顿时醒悟我(T3)的想法是多么(naive),宛如智障。

晚上的做题

晚上回宾馆,首当其冲先是在(QQ)上远程膜了膜闪指导,希望能给明天带来好运!

然后写掉了早上口胡出的那道题:【洛谷5794】[THUSC2015] 解密运算

接着又去看了看(PKUSC)的题目,又写了一道状压(DP)【洛谷5369】[PKUSC2018] 最大前缀和

发现这两天自己刷的(PKUWC)(PKUSC)题似乎都很喜欢状压(DP)啊,那很奇怪的是为什么今天下午没有考状压(DP)呢?

说实话,感觉今天的题目和(PKUWC2018)的题目完全不是一个画风啊......

(Dec 22nd)

面试这种事,与我无干

早上起来后,又乘地铁到了北大。

今天上午的安排是面试,然而,作为一名非正式的营员,我根本就没有面试的资格。

所以,在(XZY)神仙面试的时候,小叶老师就帮我找了个自习室,然后我就在里面自己做题。

出于昨天的经验,今天我很机智地自己带上了电脑。

北大还是很贴心的,居然有个名叫“PKU Visitor”的网络,专门给游客使用。只要有手机,经过短信验证,就能使用网络(6)个小时。想想幸好这次带上了我外公的手机。

先写了一道昨天(XZY)神仙介绍给我的题目,感觉还是挺简单的吧:【洛谷5335】[THUSC2016] 补退选

想到昨天(T3)莫比乌斯反演题考场式子推挂,于是赶紧去找了道莫比乌斯反演大水题巩固了一下:【洛谷4450】双亲数。纵使今天不可能再考莫比乌斯反演,即便这道题目实在太水还感觉似曾相识,我依旧义无反顾地写了一遍。

午饭

午饭自然依旧是在北大的食堂里解决的。

感觉昨天晚上吃的拉面还不错,于是又找到了那个名叫“清真·美食”的窗口,点了份牛肉手抓饭+孜然土豆片。

牛肉手抓饭味道还挺不错的(尽管没怎么吃到牛肉),而孜然土豆片更是人间美味,个人感觉这要比薯片好吃多了。

上机测试

吃完午饭,就是第二天的上机测试了。

根据昨天的经历,今天首先注意了一下座位号,是(121)号。

看到这个号码,第一反应是(121=11^2),有点不知所云。

然后再仔细想了想,发现(1+2+1=4),完了,恐怕又要死了......

开场觉得(T1)似乎很可做,一开始不小心写出了很多问题,好不容易在一个小时左右之后写出了一个二分+主席树(O(nlog^2n))做法。

结果一交发现被卡掉了,再仔细推了推,发现可以改成主席树上二分,于是就变成了(O(nlogn)),在一个半小时左右(A)了此题。

然后花了一个多小时先去写掉了(T2,T3)的暴力,接着便试着去推(T2)

又过了半个小时,似乎想出一个很复杂、需要大量分类讨论的线段树做法,写了一半之后,反手把自己(Hack)掉了。

正绝望的时候,没想到居然根据自己的(Hack)数据,又想出了另一种更为简单的线段树做法,大喜之下写了一发,居然过了,顿时无比激动。

接下来去想(T3),想了半天感觉最小割除了等于最大流之外,好像没什么性质可以利用,最终(19)分弃疗。

本来以为(219)分应该挺高了,结果发现人均(200+),人均切了前两题。而最后一题只拿了最低档部分分的我真是被人均吊锤。

晚上的事情

迷上了“清真·美食”......

晚饭点了一碗牛肉拉面和一份孜然土豆片,再次认为孜然土豆片真是太好吃了!

吃完晚饭,接下来便回了宾馆。

先是在(XZY)的指导下做了一道题:【洛谷5795】[THUSC2015] 异或运算

然后,无聊的我由于最近刚学会如何感性理解(FFT)(NTT),便想要找到多项式的题目做做。结果翻了一个晚上,发现都是些神仙题,蒟蒻我完全不会做......

今天睡得有点迟啊,毕竟上机测试已经结束,明天早上没什么安排,可以在宾馆里待上一个上午。

(Dec 23rd)

迷迷糊糊的早上

今天早上(7:20)才起来,比以往起得都要迟。

感觉依然有点没睡醒,吃完早饭后依然迷迷糊糊的。于是早上就没有写题,找了几道题,钻研了一下题解,打算等下午上了高铁之后再去写。

全聚德北京烤鸭

中午,小叶老师带上我和(XZY),约上法老去吃全聚德的北京烤鸭。

在楼下我们便遇到了一个难题:明明我们就是在一楼,结果门口一个宣传招牌上说全聚德要上至一楼。

后来才想起来,似乎英语课上教过,在有些地方,我们所认为的一楼被称作(Ground floor),再往上一层才是(First floor),即这里所谓的一楼。

进了全聚德,首先便是点菜。

我拿过菜单粗略看了几眼,发现大多数菜都是近两百元的,其余菜几乎都是(50)元以上,只有极少数的菜是低于(50)元的。不得不说这好贵啊,吓得我直接把菜单还给了小叶老师。

这里的服务员态度很周到,给我们介绍全聚德的历史,还给我们示范如何用面饼把烤鸭包起来吃。

小叶老师说尽量吃,否则就会浪费。想想这里菜这么贵,于是我就拼命吃,吃得很爽快。不过到最后,我们依然留下了很多菜没能吃完。

吃完饭已经有点迟了,所以我们直接坐出租车去了北大,然后走到双创中心参加下午的闭幕式。

闭幕式,同样与我无干的颁奖

由于我们到得有些迟,发现闭幕式已经开始了。

此时好像一道题正讲了一半,从中间开始听,剩下的一半完全听不懂。

而接下来的题目,同样也是本来就会做的依然会做,本来不会做的听了依然不懂,感觉自己依旧好菜......

接下来是重点部分,也就是颁奖,但这似乎同样与我这个非正式营员无关。

(XZY)神仙得了三等奖。

颁奖结束后,闭幕式也就结束了,于是我们匆匆离开北大,乘坐地铁,花了(40)多分钟到达了火车站,踏上了回衢州的归程。

归程

高铁在下午(3:25)出发,预计大概在半夜(10:56)到达。

下午和晚上在高铁上又写了几道题,这里贴一下博客链接:

顺便说一下,昨天晚上找多项式题目找一晚上真是血亏,今天翻了下(XZY)神仙的博客,找到一堆多项式好题。

后记

回到学校,很快又投入到了文化课中。

毕竟还是初三,还是要好好准备中考吧,不然就没高中读了,恐怕就得回菜地里去当蒟蒻了......

原文地址:https://www.cnblogs.com/chenxiaoran666/p/PKUWC2019.html