PKUWC2018划水记

  半夜在宾馆里睡不着,被潜意识叫起来写作文

  至于为什么标题是划水呢?因为冰也是水的一种形态,而长沙正好又下雪,所以你懂的。

Day -1(1.28)

  考前疯狂复习模板,正好前一天晚上打了一发LCT维护最小生成树的裸题。MD这算法果然是小C的一生之敌,做了几次link和cut操作之后总有节点开始按捺不住欲望开始做一些有悖伦理的事情,在手画了N(N>10)棵平衡树之后,终于发现是寻找一棵splay中最左的节点的时候必须一路down下去。于是放弃了直接维护最左节点的想法,改了一发,果然A了。

  看一眼时间,凌晨2:00,身心俱疲,而且感觉自己菜得没边了,感觉药丸。

  一觉起来10:00,突然航空公司打了个电话来说因为长沙下暴雪,航班取消了,家长各种急然后各种商量最后订了高铁之类的云云。然而高铁的情况也不容乐观,因为下雪的情况各种延误,而且基本都是延误2h以上的。大概是因为等待的乘客太多的缘故吧,乘坐高铁后来竟发展成为了一种类似于挤公交的模式,只要要去的地方正确就行,票对不对得上都不管了,车站的工作人员都已经开了绿灯。尽管如此,到达长沙的时候已经凌晨1点了(原本预计前一天晚上9点到)。

  感觉药丸(x2)。

  说一说在列车上的事情吧,看小F打以撒明明拿了寻人启事不去解锁lost偏偏作死去打boss结果被锤死各种心疼,本来想复习一波数学却毫无心思,开着网易云把为第七届东方人气投票准备的歌单里的14首歌循环了N遍。

Day 0(1.29)

  一觉起来9:00,打开窗帘woc外面屋顶积雪好漂亮!因为冷所以点了外卖,热干面差评,不如福州的拌面好吃。中午去长郡报到领活动安排表(居然不发狗牌),顺便dfs附近的小吃店估摸着早餐在哪里解决,最后还是锁定了金拱门这一最优解。

  顺便在长郡报到时看到了满地积雪,小C怎么也控制不住自己往“澄池”旁的积雪上反复踢蹬的右脚(尽管在旁人看来这个动作可能很傻),但是作为一个从未如此近距离接触过雪的南方人,遇到积雪的第一反应肯定也是这样吧?

  回宾馆和小F还有两个学弟划水,划久了竟然划出了罪恶感,正好电脑没电了,回房间充一波电顺便打一打回文树模板。打到一半不知道为什么被叫去和同省某校的选手一起吃晚饭,觉得迷。而且这里的菜属于小C不太对付的“辣”,感觉肠胃隐隐作痛…… 感觉药丸(x3)。

  回房间打完回文树,开始恶补数学,看各种不等式,看高中数学联赛卷子,圆锥曲线根本不会所以干脆不看了听天由命。小C我是搞数竞的人怎么还能死在数学上的啊??(flag)


Day 1(1.30)

  早上6:30起床,各种困,但是吃了金拱门之后精神++。

  8:00开营仪式,不知道为什么PKUWC上在放长郡的宣传片(还是2014年拍的),觉得迷。

  听副院长普及各种知识,还有练习题做。但是感觉越听越困,精神--,感觉药丸(x4)。

  结果真的药丸。看到考数学用机试之后显得有些惊讶(小C乡下人见识少)。

  开始答题,就不知道为什么坐在小C左右的选手屏幕上显示的题号总是比小C显示的题号多7呢?小C怎么也想不明白。

  该复习的都没考到,卷子里一股子高联初赛的画风,选择题50%是初中奥数题,立体几何这么简单不是送的吗,被三四道奇怪的题目卡住,果断选择跳过(蒙答案)。

  然而小C还是做得好慢啊!还有45min给小C做后面4道大题。

  看到第二大题,小C的心悸动了一下,这不是计算几何么,一波向量搞上去……然后什么也没出来。

  还剩10min,好像第三题可以用均值不等式!先做差法,再展开,我写……

  MD出来和学弟一交流发现自己写了假的均值不等式!!(具体怎么假小C就不说了,太丢人了)

  这样数学的分数就是 60- 了,心态爆炸,感觉药丸(x5)。太鸡儿丢人了,还好意思说自己是数竞的。

  中午短得就像白驹过隙,回宾馆小坐一会就要出发,这之间顺便复习了一下2-SAT。

  下午上机测试,名正言顺的Day1。

  点开T1,题面有“小C”(好感度++),是概率问题(好感度--);

  点开T2,题目是“Slay the spire”(好感度++),题面有“九条可怜”(好感度不知道该加还是该减);

  点开T3,题目是“斗地主”(好感度--),题面是“斗地主plus(plusplus……)”(好感度=-INF)。

  所以果断开始做T2。

  对于每一种抽牌的情况,按照强化牌的张数和k的大小关系分类讨论,可以得到各自的贪心策略,这两种贪心策略似乎都可以用O(n^2)DP来计算答案?

  脑子很乱,写了一个小时才搞出来,交一发,WA,20分,心态崩了。

  各种尝试+肉眼观察法调代码+重交了若干发,20min过去了,max(分数)=20。

  或许小C应该为这场比赛不是NOI赛制而是IOI赛制而感到万分庆幸?

  开始尝试写暴力对拍,发现暴力过不了样例,尝试肉眼调试,无果,心态(真的)崩了。比赛已经过去2h……

  已经处于弃疗状态的小C开始把过不了样例的暴力和WA掉的正解放在一起对拍。其间电脑因为有文件扩展名变更的缘故一直发出“咚”的系统提示音,声音大到全机房都能听见的那种,幸好大家都在专心码代码没有过多计较。

  发现居然拍出错了!!!!!原来是小C的标程对k=1的情况处理得不够到位。

  改完一交,发现过了,当时眼泪都出来了。

  (出题人你过来一下,头伸过来一下,k=1的数据点你居然放了8个!?这么出数据不怕走路被古明地盆砸么??)

  还剩2h结束,马上开始打T1暴力,很快过掉了40分,50分需要压一压空间,但是小C想先肛一下正解,想不出来最后剩30min再打,应该……能打完吧?(flag)

  然后想了各种骚东西,推式子拆式子之类的,然而并没有什么卵用。

  有想过启发式合并,然而当时不知道为什么那根筋抽了,认为“dsu就是枚举小的,在大的里面查找,而这道题是两边都要枚举,所以不可行。”

  所以只剩30min了,乖乖去打50分暴力,还差点没调出来,剩2min的时候终于拿到了50分。(丢人,你退群吧)

  (10分?10分也是分啊!一道数学大题的分数啊!

  所以Day1 150分,排名rank19~40+,因为这一排名段都是150分的人。感觉药丸(x6)。

  小Z想到了T2 DP方程却没有想到贪心策略,小G想到了贪心策略却没有想到DP方程,他们还真是能打。

  晚上复习了一下后缀自动机的板子,感觉自己萌萌的。

Day 2(1.31)

  早晨依然6:30起床,但是晚上还是没睡好的感觉。但吃过金拱门之后精神++。

  名正言顺的Day2。

  点开题目一看,其中两道题目带有“随机”字眼。然后这三道题不是计数就是期望……两天出了五道数学题和一道斗地主?!

  出题人你再把头伸过来一下……

  选择题目名字中不带“随机”二字的“猎人杀”入手,各种难下手……

  然后发现过掉T1的人数正在飞速上涨!!woc如果签到题切不掉我岂不是要凉?

  开始搞T1,在O(3^n*n)的基础上开始优化,想了很多骚东西,比如折半搜索啊,一个大小为x的联通块的最大点独立集不超过x/2之类的,然后想能不能剪枝,通过捣鼓了一番计算器,(强行)觉得能过,就开始写代码。

  然后发现空间不够,要hash!于是悬崖勒马。回头一看已经有60+人过了T1,心态(又)崩了。

  于是去上了个厕所……

  回来一坐到位置上,不知道哪根筋搭错了,开始想:一个连通块内的最大点独立集的个数似乎不会很多……?

  考虑O(2^x)搜出每个连通块内的所有最大点独立集的方案,每个连通块的贡献是独立的,然后每个连通块计算答案就相当于统计合法的拓扑排序(虽然后面发现和拓扑排序还是有一点不同的)方案?这玩意儿就可以用O(2^x*x)的DP解决了,所以总复杂度是O(k*2^x*x),k为一个连通块内最大点独立集的方案数。大概估算了一下,x=20的时候,k最大的情况大概是每5个点组成一个团连在一起的图,k≈150。又因为复杂度绝逼不是满的,于是就开始写。一发就过了。

  看了看榜,过掉T1的人数还在增长,而考试已经过去了3h。傻逼题都做了这么久,感觉药丸(x7)。

  拿下T1,根本不敢贪心,先把T2的30分拿下,一发过,看了眼时间:3h16min。突然被自己的代码能力惊到。(你们真的不要再D小C这个蒟蒻了)

  在想能不能搞出T2的50分,又想了很多骚东西,比如容斥啊,不同权值的只有sqrt(Σwi)种之类的,但还是无果。

  剩下30min去看T3。期望题?好像有听小D讲过高斯消元什么的……

  尝试性写10分的数据,发现根本不会列!方!程!

  我tm学了假的期望……(或者说,我可能有个假的脑子……)

  然后开始回忆以前做过的期望题,好像会列方程了……然而只剩10min了……

  剩下10min小C基本都是以弃疗的状态在写代码,反正没写过就随便写写……然后以至于程序内出现了大量名字长度为4的意☆义☆不☆明(或者说意义相当明确)的变量或变量数组……

  Day2 分数 130,rank50+~100+,感觉自己菜到姥姥家了……感觉药丸(x8)。

  然而140分的人数是rank20+~50+……

  两试平均起来应该能挤进前50吧?然而担心自己的数学炸裂……

  小Z都拿了130,然而小G似乎发挥得不太好,不过他们还是能打的人。

  所以小C Day1+Day2=150+130=280。

  怀着忐忑的心情,又到了下午面试的环节。

  本来说是14:00发面试名单,然而硬生生拖到了15:00。

  小C出乎意料地排得很前,大概在25名左右吧。然而这也间接导致了面试很快(15:10)就轮到小C……

  老师A是个男老师,再加上几乎没有准备,所以小C回答得十分僵硬……不一会就出来了……

  看到老师A在小本本上给每个学生打分,前面的的两位选手都是80多分的样子,然而在小C的名字后面赫然写着个“7”,后面不知是“6”还是“9”,和小C谈话时不停地描着后面那个数字……

  小C的心好凉……感觉药丸(x9)。

  反正还有1h第二次面试,好好准备一番就行……

  老师B是个女老师,开心。与其他老师画风不同的是,老师B桌面上屹立着一台电脑……感觉更多了几分威严。

  开场做了个先抑后扬的介绍,成功吸引老师的注意,然后小C厚颜无耻地扯到了自己的blog。

  老师似乎饶有兴趣的样子,还问了访问量如何之类的话,好像get到了加分点?

  听说把这位老师的视线从电脑屏幕转移到你身上来就算还行?……

  老师C因为篇幅限制就不写了……反正猜着你们也不想看了……

  晚上逛B站,补番ygo。

Day 3(2.1)

  PKUWC真的要接近尾声了啊。早上还是金拱门。闭营仪式有两个小时,反正猜着也是讲题解。

  屏幕上还在播长郡的宣传片……重新温习了一遍,发现还是自家学校的历史更悠久一点。

  面试小C的三位老师中,有两位在台上主持,敢情面试小C的都是boss级别的啊。

  这两天的题目是吨老师和吉老师出的,瑟瑟发抖。

  听大佬们讲完了D1T1,突然发现这是道傻逼题,其实就是动态开点的可持久化线段树的启发式合并。小C反思了很久,没有做出这道题确实是对不起自己的水平了……也许脑抽是一种原因?题目的式子太奇怪导致自己想多也是一种原因?IOI赛制导致的满足心理又是一种原因?但既然考场上没有写出来,就说明自己确实不够熟练,还是要继续努力啊。

  D1T3看来是被狠狠吐槽了一番啊,虽然结论推起来应该不是很难,但是代码实现的各种细节要想在考场上完成是非常困难的,谁愿意在自己没有拿到前200分的情况下去冒险写这样一道题呢?顺便挂一下吉老师(作为出题人)在知乎里对这道题的评价

  D2T1各种神仙交流,很高兴听到第一个上来的同学说的就是我的做法,然后后面又有选手一言不合上来hack很恐怖(虽然我觉得这种做法不一定能被hack掉),后面又听了各种O(2^n*n)的做法,感觉全世界写了这么傻逼的做法的只有小C了。

  D2T2是推式子题,上来交流的那位山东高一选手果然强,对题型的转化也让人有一种醍醐灌顶的感觉,虽然后面推式子把大家推得一脸懵逼的样子,但是小C还是发自内心给他鼓了掌。标解用的是生成函数,在用到生成函数之前还阐释了式子的组合意义,脑海里不禁回想起一个月前那个等公交的晚上小D的低语:“不搞懂组合意义的话,光推式子是没有前途的。”

  D2T3算期望果然是高斯消元,还要分个层,又是神仙交流,然后山东小哥又开始虐场,果然强,找个时间把这道题打一打吧。

  讲完题解突然开始播校庆宣传片,好听!

  拍了0.5h的集体照,上来领协议。

  由于不知道念协议的顺序,所以小C一直等得很焦灼,只见那位念名字的老师(就是面试小C的老师A)拆了若干个文件袋。小G和小Z都先后上去了。

  讲道理名字越晚出现应该越稳才对,但是中间冷不丁出现的一些明确比小C分数高的大佬的名字还是让小C有些怵的。

  好像是省队本一……大概是第二档吧(然而这一档是大众分233),第一档应该是NOIP一等本一。

  真的好像做梦一样,感觉这两三天发生的一切都像是在做梦一样,如梦似幻。

  然而还有省选呢……三场连战还真是令人一刻也放松不下,总之早点休息吧。

原文地址:https://www.cnblogs.com/ACMLCZH/p/8402557.html