THUWC2019滚粗记

Posted by wyj on January 21, 2019

Day0

拿着一个天上掉下来的奖励名额,知道绝对不可能签到约的我毫无压力的来到了广州二中。我妈居然没带身份证,费了很大一番周折才住进酒店。看见很多穿着丑陋无比的绿色面口袋的学生。走了很远的路去万达吃饭,繁华的都市生活和农村臭水沟就只隔着一条马路。晚上没有打已经报名了的CF,去探索了一番酒店有没有ipv6。后来发现CF全场都AK了。

Day1

早上去报到试机。熟悉的Ubuntu 18.04,可惜没有root权限并且不敢提权。配置了半个小时gedit和VSCode。试机开始了,一看题,两道不会做的原题。于是我就一道题都没写直接走了。大家出来之后交流信息,震惊地听说某三个人试机时看了Day1的题目。然后他们就被关在体育馆里一直不让出来了。好惨啊。

中午吃饭+合影。下午开始做(bao)题(ling)。一开始觉得T2超可做,送了60分,然后想了一个多小时,觉得标算呼之欲出了,此时听见解释题意。按照墨菲定律果然听错了。然后稍微改了下思路,写了个60%的讨论。写炸了,居然被我鬼使神差地全部删掉了,白白少了第二个subtask的60%.

此时比赛时间已经过半,我得分为0,赶紧开始码暴力。T2码了42分,就是一堆普及组算法拼起来,居然(按照我的码风)码了122行。然后开始看T1,不动脑子码了个暴力,然后开始观察性质,无果(这么明显的性质我居然观察不出来,果然是越来越菜了)。随便码了一个没分的只有1到2的\(O(n^3)\),观察规律。发现这每次的取法居然是独立的。我TM鬼迷心窍没有继续想下去,然后就弃疗了。

此时还有30min,T3码了一个dfs,还自我感觉良好以为有分。果然TLE。这肯定是要垫底了,最后还是垂死挣扎了一下码了一个状压,没有爆零。一下午的感觉就是人生第一次VSCode用的超爽。预计得分12+42+10=64。

出考场交流发现果然垫底了,随便谁都比我高100+。T1那么傻逼一个式子我硬是没看出来,全场都切了,T2所有人都会60%,T3snz会20分的容斥。还是在我的预料之中,之前在本校的训练大多数时候就是这个样子。现在可能心理素质要高一些了。

晚上去开营式,听清华自吹。

Day2

早上困得要命,起不来床。进入考场,没有配置gedit,打算只使用VS Code了。有一道交互题,要重写一个tasks.json。首先三道题都看了看,不太会。然后集中精力看T1,看半个小时,大概会了一个\(O(n\log^2n)\)的做法。尽管是50万,但是树状数组和树剖的log都不算log。我写了一个半小时,大部分的时间居然一直在调试树状数组。我从来没有写过单点赋值区间查询的树状数组(一般写的是单点加),所以写错了很多次。

然后我信心大增,昨天还没拿分的时候今天已经拿了100分了。开T2,首先不动脑子写了个32,怎么样例都过不去?原来是我智障地认为feature2在只传两个点时一定返回中点。然后写了个真的32,\(\frac{n^2}{4}\)次询问。然后我思考能不能拿更多的分。由于很容易就可以求出树的重心,我考虑点分。一开始以为17分很稳,后来发现写了个假算法,判断某个点属于分治中心的哪一个儿子是\(O(n^2)\)的。具体来说,一个菊花图,每个点下面再挂一个点就卡掉了。然后不想放弃,想要一个log找属于哪个儿子,又想了一个假算法。我以为可以像“老鼠喝毒药”那个问题一样判断,都写完了才发现无论包不包含“毒药”feature1的结果都是一样的。弃疗了。

居然只剩半个小时了,我数据范围都没看就开始码T3的34分暴力,随便拍了一个凸包,不知道对不对。样例和大样例都太弱了。还有5分钟的时候我终于调对了。预计得分100+32+34=166。这个day1和day2好像出反了。

出考场发现果然垫底了,T1全场切并且都是一个log,T2全场的\(O(n^2)\)都能过60(据hlh说这是普及组难度的cdq???),T3全场都会\(O(n^4)\)dp。后来发现T1把树剖直接换成括号序列就可以一个log了,考场上失智没想到。T3 dp非常裸,可我没时间想了。不知道为什么T2的60分可以过菊花图。肯定是没戏了,明天可以清闲了。

下午就写写游记,睡个觉。洛谷打卡大凶,loj也是凶。觉还没睡够就被叫起来吃外卖。吃完晚饭就去Day2+。我把我所有的赌注都押到这场上了,痴人说梦希望翻盘。开题,一看都是些图像处理类型的题目,我不是很懂。好像全都只是暴力按题意模拟,提交答案。不动脑子写了adler和crc32校验。可惜没有Free Pascal,不然一句uses crc;A题。(UPD:发现世界上只有我一个Ubuntu盲不知道系统自带crc32)

然后开始读入输出png。我当时目光短浅,只考虑到读入,于是想转成ppm类型直接读。没有我习惯使用的KolourPaint,我试验了几个自带的软件:GIMP(不知道THU是出于什么目的装这个),Shotwell,Image Viewer,全都不能转换。忽然灵机一动想起来我曾经是如此处理ppm的,试着打开ImageMagick,果然灵验。于是不动脑子完成了png的读入。

下面是png输出,这时我发现小聪明失效了,用ImageMagick转出的png和题目要求的“简易png”不兼容。还是认认真真读题吧。把题面翻来覆去读了四五遍,终于读懂了这个超级复杂的”简易”格式。码农了一个多小时。发现我包含很多错误的png输出完全能够正常显示,Image Viewer太智能了。终于过对拍(即diff)时,只有25分钟了。

争分夺秒地码边缘识别。不就是一个矩阵卷积嘛,把题目给出的式子直接码进代码里就行了。可惜手速不够,写完的时候只剩3分钟了。运行一下,效果出奇的好。如此简洁的式子居然能够做到这么漂亮的结果,对前人的智慧感到敬畏。预期得分20+30+50+50+20=170。

出考场发现终于没有垫底,但也不算翻盘,也就一般般而已。

Day3

早上压根就没有准备面试。非常忐忑地听面试名单。首先是hlh和snz两位大神,然后是lmq(第二批)。快报完的时候我觉得没戏了,这时候忽然听到了自己的名字。喜出望外的同时更加紧张了,我想这次肯定不像初三时那样容易过关。被带到机房准备面试。大家居然都在使用电脑,完全无视禁令。我看到旁边的大神打开了luogu,输入了一个id:@shadowice1984。久闻大名,如雷贯耳,没想到有朝一日能够见到他本人。看他浏览自己咕值第七的排名,看自己博客里汗牛充栋的题解(我有没有滥用成语?),我难以表达心中的敬畏。更让我震惊的是,黑板上写着一个网址。非常和谐。

在默默膜拜身边大神的同时,我也一直在提心吊胆地给自我介绍打腹稿。直到叫我去参加面试的时候我才差不多想好了。面试的时候有3个考官(上次只有一个),两男一女。自我介绍和上次一样卡壳了。居然没有谈人生,也没有提我380分的NOIP。数学题和上次一样傻,简单鸽巢原理。英语比上次难很多,第一个词Associate就不认得。整篇文章看得半懂不懂的。(现在我知道了,这是我超喜欢的<ext/pb_ds/assoc_container.hpp>里面的assoc,也是THUSAAC里面的A)。面试时考官一直在笑,心里很虚。面试完一出来就迷路了。因为我姓名音序太靠后了,题解一道都没听到。

下午很放松地听讲座,放了看过不知道多少遍的视频。我一直在颓废,没怎么听。到了放约的时间了,我又紧张起来。咕咕了一个小时才终于开始。这次招生办的人说政策改了,只给一二三等奖。为了官老爷们阻止阶层的流动从而促进社会和谐稳定,条件又收紧了。hlh首先拿到了约,居然只是二等奖(省队一本)。我以为是按成绩顺序放约的,心里很慌。然后是lmq,只有三等(再来一次)。我更慌了。过了好久之后是snz,他拿约回来的时候所有人都说什么“稳”“内定”之类的话,肯定是一等了(相当于无条件)。很快就是我自己,二等。仔细想了一下,我进省队的可能为零(NOIP380;我校高二很强可能会到达1/3限制;最坏的是没有C++11我什么都写不出来),所以这还是一个废约。这个结果也就算一般般吧。

晚上夜游了酒店的小花园,然后写游记。除了我所有人都有WC资格,我明天就直接回家了。游记完。