THUWC 2020 游记

## THUWC 2020 (2019?) 游记 ### Day $-?$ THUWC 恰好在学考后一周，因此考完学考就进入了紧张的~~准备~~摸鱼中。停了两天课，还错过了学校里 IMO 二度金牌爷的讲座。 停课前打 USACO，在一道区间 dp 上卡了 3 h，最后交了一个假做法强行把那道题过了，剩下的就没有时间写了；后来发现 T2 是一道还比较可做的树上问题，没写有点亏了。停课的时候打了 Codeforces 的一场 Virtual Contest，感受了很神奇的暴力；又做了 COCI 的 Contest 3，感觉比去年的 COCI Open 难多了，竟出现了代码极长的淀粉质，直接放弃实现了。 感觉写的题目还是不够多，似乎本来可以写更多的题的。 ### Day $-1$ 为了机票便宜先到 TJ 中转。零下的温度感觉确实比较冷，但是也没有预想中那么冷？需要穿的衣服居然没有超过 $3$ 件。飞机上凭印象写了 NTT，居然默写正确了。 总感觉休息不足，非常困的样子。 ### Day $1$ Day 1 要从 TJ 出发，体验了一下复兴号的城际列车，确实比 D 字头的车快了不少。接着乘地铁去报到，发了一个有花纹的布制品，本以为是格子衫，仔细一看，“精品围巾”。嗯，说实话出于某种原因我还是比较想要红色的围巾（bushi。 报到完就试机，这回是在系里的实验室考，电脑的系统似乎是 XUbuntu，不支持 Ctrl-Alt-T 打开终端似乎有些不习惯。看了看电脑里奇怪的软件，似乎只有 GIMP, Golden Dict 这两个，考虑到去年刚考图像，难道这回要考嘤语？桌面上还有 en.cppreference，难道要考毒瘤语言特性？反正根据这些信息，暂时猜不到 Day 3 考什么。 注：题意简述可以在 [ouuan 的博客](https://ouuan.github.io/THUWC2019-%E7%AC%AC%E4%BA%8C%E8%BD%AE%E5%86%AC%E7%9C%A0/) 找到。 #### 试机 试机 T0 是 A+B，打了快读把它过了。 T1 是一个有点奇怪的题目，大概是说有 $n$ 个 A 类物品，权值分别为 $a_1,a_2,\cdots,a_n(a_i\in \mathbb{Z})$；有 $m$ 个 B 类物品，权值分别为 $b_1,b_2,\cdots,b_m(b_j\in \mathbb{Z})$。现在请你把这些物品从左到右排列成一排，计算总权值如下：对于每一个物品，如果它左边的物品与它同类，那么它对总权值的贡献即为 $a_i$ 或 $b_j$；否则它对总权值没有贡献。特别地，最左边的物品对总权值没有贡献。要求总权值的最大值。似乎是一个奇怪的贪心，花了一些时间想，最后玄学地通过了。 T2 好像是一道奇怪的树上计数题，模数是 $998244353$，而且旁边的选手还嚷嚷着让他的同学帮他调 NTT……看来这题不可做，直接跳了吧。 T3 是一道字符串，给一个字符串 $A$ 和 $q$ 个字符串 $B_i$，要把 $B$ 插入到 $A$ 的某一个地方（比如 $A=abc,B=de$，那么可以得到 $deabc,adebc,abdec,abcde$ 这些），求插入到哪里时得到的字符串字典序最小。照例是不会做，所以直接用 `string` 打了暴力，居然拿了 $40$ 分？ 虽然试机有好多不会，但是反正也不太在意吧，所以也没有影响心态。 中午急忙吃完饭，就回去合影和开幕式了。合影意外地没有拖太久，开幕式也进行得极快，“讲 $8$ 点”值得好评。 于是就到考场就位，略作等待之后，Day 1 就正式开始了。 #### Day 1 T1 一道很有意思的题目。 首先写了暴力，交上去拿点分爽一爽。因为觉得题目情景不复杂，所以便思考正解。我思考的点是“预处理当前工资计划是 $i$ 时，最终的工资计划应该是什么”，由于 $k$ 很小，因此对每一个员工弄了一个单调队列，在单调队列上二分。后来发现这样确实可以通过，而且预处理时怎么做，查询时也相应地怎么做。于是花了约 $1 \mathrm{h}$ 愉快地通过了。 #### Day 1 T2 一道比较恶心的题目。 首先把比较容易的分数写了，接下来的却没有可以快速实现的思路了，于是决定去写 T3。 #### Day 1 T3 首先把送的 $8$ 分拿到了，接着又陷入了长时间而无效的思考中…… 据说北方冬天开了暖气的室内比较催眠，这是真的。再加上昨天晚上不适应这里的环境没有睡好，所以真的是越想越想睡。 强行去洗了洗脸，好不容易清醒了。回来看看还剩下的许多时间，决定回去写 T2。 T2 有一个“树”的 $13$ 分，似乎可以用树剖暴力地解决掉。再看一眼时间，写吧。 于是开始写树剖、线段树。时间过得很快也很慢，我不停地写啊写啊，简直都不知道自己在写什么。`dfs1`, `dfs2`, `build_tree`, `pushdown`, ... 终于似乎是写完了，我甚至都不想再看代码，直接跑样例。修改了一点小的错误后，过了样例。 直接交！猛按几下 F5 过后，那个测试点旁边显示出了 Accepted 的文字。什么？我默写的树剖就这么通过了？我不放心地再浏览了一遍代码，找不出明显的问题，才终于判定——树剖应该是写完了。这是我 OI 生涯中至今考场上写的最长的代码了吧，总长度近 $400$ 行，大小近 $10 \mathrm{KB}$，可惜不能带回去纪念。 还剩大约半个小时，剩下的点似乎怎么也过不了，T3 也毫无思路。最后在玄学修改程序中~~度过~~消磨了最后半个小时。 #### Day 1 总结 Day 1 的话题目确实超出了我的水平范围吧，不过好在我在 $2.5\mathrm{h}$ 时放弃 T3，并决定去写树剖，否则后半段真的要一无所获了。 ### Day 2 早上早起到西郊宾馆吃了早餐，种类还算比较丰富，大吃一顿后上了大巴。大巴上照例听了 Euphoria。 同样稍作准备后就开考了。 #### Day 2 T1 一道比较神奇的题目。 有 $n(1\le n\le 15)$ 个函数 $f_1,f_2,\cdots,f_n$，每个函数形如 $f_i(x)=a_i\vert x \vert+b_ix+c_i$，给定初始值 $x$，你需要安排函数复合的顺序，使得最终函数值最大；也就是你需要给出 $1\cdots n$ 的一个排列 $p_1,p_2,\cdots,p_n$，使得 $f_{p_n}(f_{p_{n-1}}(f_{p_{n-2}}(\cdots(f_{p_1}(x)))))$ 最大。$x,a_i,b_i,c_i\in [-15,15]$，允许使用 `__int128`。 首先还是写了 $n\le 10$ 的枚举暴力。接着注意到 $n$ 很小，回想到我在 THUSC 2019 吃的亏，考虑状压 dp。状压 dp 要满足子问题最优特性，为了满足这一点，我在草稿纸上画了一下函数的图象，发现 $f_i$ 一定是拐点在 $y$ 轴上的一条折线，在 $y$ 轴两侧都是单调的。因此，使得 $f(x)$ 最大的 $x$ 只有四种可能：最大的正数、最小的负数、最大的负数、最小的正数，也就是 $\pm \infty$ 的极限和 $0$ 的左右极限。 因此就有了一个很诡异的方法：把状态记为已经复合的函数的集合，也即 $p_1,p_2,\cdots,p_k$ 的集合；对每一个状态维护可能达到的“最大的正数、最小的负数、最大的负数、最小的正数”这四个值，转移的时候把前驱状态的所有结果塞到函数里，排个序，再把最小值、最大值、$0$ 的前驱和后继全部塞到新状态的 `vector` 里面就好了。 没想到这种看上去十分暴力的解法居然过了，不过其实它的复杂度似乎是正规的 $O(2^n\cdot n\log n)$。 #### Day 2 T2 还是照例先写暴力，接着总觉得“部分分好像都可做”，然后去打部分分。首先是把 $a=1$ 的 Subtask 4 写了，然后发现自己欠考虑了，连稍大的样例都没过。接着就强行打补丁，把漏考虑的情况写了写，终于过了这个 Subtask。其他的 Subtask 好像也有些可做，我甚至还写了 Subtask 3 的程序，可惜是个假做法。想要打补丁，可越想情况越复杂，但写了代码又舍不得放弃，况且 T3 的劝退模数又让我不禁接着想 T2…… 换题的时间到了，我最终还是放弃了其他 Subtask，把过了 Subtask 1,4 的代码重新交了上去。 #### Day 2 T3 写了暴力，结果暴力超时了，只拿到送的 $1$ 分…… 实在是太自闭了，在本地一看，$n=10$ 的预处理就要跑好久好久……根本过不了啊。 看来纯暴力是不行了。我再想了想，可以不用处理 $A_{10}^1+A_{10}^2+\cdots+A_{10}^{10}$ 种排列，只需要处理 $1!+2!+\cdots+10!$ 种，最终把诸如 $3,9,1$ 这样的排列映射（离散化）成 $2,3,1$ 就好了。加了这个小优化，尽管本地跑得还是很慢，但是交上去居然过了？ 旁边的同学其实给我一定压力，他不停地（真的是不停）大声（真的很大声）击打（真的是击打）键盘，嗯…… 在想到“排列映射”的时候，我有了一个偷懒的想法：会不会“满足某种特征”的排列，它们的答案是一样的呢？如果找到这种“特征”，那我就不用写映射了。事实上，只要找到了“特征”，再加以打表，就可以告别暴力了！ 于是我走上了漫长的打表之路。首先根据冒泡排序的特征，第 $k$ 轮后，第 $k,k+1,\cdots,n$ 大值一定是已经归位的；因此如果没有归位，答案一定是 $0$。 接着，我观察到，顺序排列 $1,2,\cdots,n$ 的值很有特点；而其他排列就是在部分重复顺序排列的答案！只是重复的不太一样，有的重复的是 $n-1$ 的，有的重复的是 $n-2$ 的。 是什么决定了它重复的是哪里的呢？我首先试了逆序数，因为题面里提示了“逆序数不断减少”，但是并不对；我又尝试了“$n-1$ 的位置”、“$1$ 的位置”等奇奇怪怪的指标，发现都不对。 还剩一个小时，真是自闭啊。更神奇的是，旁边的同学还小声喊了一句，“我找到了”（之类的话）…… 最终鬼使神差，我找到了规律——把这个排列做**一轮**冒泡排序（只做一轮！），这一轮中交换了 $k$ 次，那重复的就是 $n-k$ 的顺序排列的前几个答案。真是……神奇啊。 然后就是写咯，知道规律了就能多拿好些分，但是更复杂的 Subtask 由于我不知道如何维护信息所以也写不了，最后还有约二十分钟的时候算是结束了所有可得分代码的书写。 #### Day 2 总结 Day 2 的启示主要就是要放弃吧，要是我不停地肝 T2 那恐怕是什么结果也没有。然后就是要坚持打表，即使一时找不出规律也要硬着头皮找（大雾）。 ### Day 3 (Day 2+) Day 2 考完回去好好睡一觉，其实没有睡多长时间，就到 THU 的食堂体验了一下。THU 的食堂真的非常超值，$4$ 元的排骨简直有 nnsz 两倍的量，这也许就是我们在那里买饭卡只能使用 70% 金额（充 20 可用 14）的原因吧，专项补贴挺多的。 由于 THU 的食堂太超值了，所以我吃不完，在还有不到半小时开考的时候骑车赶去考场。 到了考场发现笔不见了，我只有一支笔啊啊啊，这还是学习题，要做笔记的啊啊啊…… 最后强行镇定下来，决定用 gedit 做笔记。 进场拿密码条，看到了“简单 Cache 系统实现”的标题，然后就在脑内回想，“关于 Cache 你有什么印象”，答案是什么印象都没有（雾），只知道这个东西和卡常数有关。 然后开考了。开考发现学习手册不知道在哪里，以为是我没找到，结果大家都没有。监考说“大家先看题吧”，结果这题没有学习手册根本看不懂，什么“Cache 一致性协议”，“MESI”？但是我“因祸得福”地看到了 T2 的一句话“这些算法的实现难度不一，请选手自行选择”，就明白了一定要做好放弃的准备。 终于发学习手册了，并且考试结束时间延迟 $5\mathrm{min}$。后来发现这 $5\mathrm{min}$ 可能让我多拿了几十分。 先花了约半个小时看了学习手册，并且认真地用 gedit 做了提纲（没有 Typora，不能写 Markdown，不能看着左边的“大纲”，真不爽）。看学习手册的时候有意识地跳过了“伪最近最少使用”和某名字特别复杂需要参考论文的算法。可是看到最后的“Cache 一致性协议”就非常难受，不停地有“看不懂”的感觉，不过还是硬着头皮扫了扫，发现后来都是技术性内容，所以就跳过了。 看第一题，就是 Cache 一致性协议。而且就是要实现那些技术性内容。 好吧好吧，我写我写。把状态编了数字编码，然后照着状态转移的表格写了下去，由于以为后面的题目还要用到这个程序，我稍微注意了一下接口的实现（虽然还是一个很丑陋的过程式接口，没有 OOP）。写完照着样例调了调，发现出入还挺大，最终发现是我把不需要打印的 `Flush` 事件也打了出来。调整之后，就通过了。 第一题就把学习手册最后的内容给写了，那后来岂不是要很难？ 结果看了第二题，发现考的是前面的“Cache 替换算法”。呃，这个不是很简单的数据结构的应用么——除了被我放弃的“伪最近最少使用”部分（这个比较难写的部分拥有其他部分两倍的分数）。再看一眼范围，$n\le 16$，本来都把堆的头文件引入了，干脆暴力了吧。暴力写完调一调，发现过不了样例？最终发现是自己被 T1 惯坏了，没有理解好“块”的概念，于是又重读 Cache 映射方式一节。经过几次尝试终于把“块”处理好了，这段处理“块”的代码也在之后的几道题一直沿用。 接着看 T3，只读 Cache 实现？充分利用 T2 的代码，似乎不难写好。原来 T1 那些复杂的东西在后面的题目都没有用啊。 还有一点时间，写一写 T4——读写 Cache 实现？似乎也不难吧，不就是要处理一下“脏”数据（没有与主存同步的数据）嘛。认真思考了一下，一个数据只有在写 Cache 的时候才有可能被标记为脏，只有在从 Cache 写入内存的时候才能消除脏标记，因此在这些时候对应维护好脏标记就行了。 写完发现不对，检查了输入数据的部分，发现脏数据部分要先读后写。改成先读后写之后还是错了，还剩几分钟，确实有些紧张，想着“也许这个调不出来了”。后来重新审读了那一段代码，发现问题是，改成“先读”之后读的数据把原来的脏数据覆盖了，“再写”的时候写的就不是那份脏数据了。于是把脏数据用临时变量存一下，就解决了。 交上去发现“$0$”和“$1$”的部分过了，“$0,1$”混合的部分却没过。仔细想了想，大概是因为“伪最近最少使用”出现了的缘故吧。 T5 是“某算法”实现？看上去完全不可做，但是它的题目和 T4 基本相同？想着出题人可能会放一点水，我把 T4 的程序交了上去，结果过了好几个 Pretest，也许白得了几十分啊。 最后还剩不到一分钟，就把我写的大纲交到 T6 “期待你的声音”上面去了。 比赛结束后看了看“伪最近最少使用”，其实也不是特别难写，但是要是我真的写了这种算法怕是要少几十分。又看了一眼“某算法”的论文，十几页英文论文。。比学习手册还长不少。我知道 Golden Dict 是什么用的了。 虽说我那几天停课也曾看过几眼嘤文论文，是一篇“$O(n)$ 点分治”的（把树分成 $O(\frac{n}{\log n})$ 块之类的，一看就觉得常数很大）；但是这么长的，实在是…… #### Day 3 总结 感觉这场发挥非常好，应该是我目前学习题的极限了吧。 做大纲这一点应该挺好的，这样我对整个学习手册的内容就有一个把握；另外“想好什么东西在什么时候会改变”应该也挺重要。还有就是调试要有一定的信心，不要总想着自己会写错很多地方。此外要学会放弃！ 停课那几天写了 CyaRon 语言（虽然是用 Python + regex 水过去的）、时间复杂度、LOGO 语言这些题目，也算是增加了学习题的信心吧。今后还可以把宝牌一大堆给补了。 ### 面试与宣讲 考完机试还挺有信心，觉得这回应该能进面试了吧。 结果从 7:50 等到 8:10，一直没有电话。8:10 我去吃饭，在西郊宾馆餐厅等到 8:40，还是没有电话…… 心里想着“我哪里写炸了呢”，然后又考虑早上去哪里玩。 结果 9 点左右突然接到我妈电话，说我爸刚刚接到电话。不是说好的 7:50~8:40 通知面试吗？然后我问“什么时候要去？”——“现在。”还好我早餐吃得差不多了——要是我决定去北京三环内玩，那我岂不是已经赶不回来了？ 整理了一下仪容仪表——在此特别感谢我爸出发前帮我剪的头发——就去会议室报到了。之前有看[ ouuan 的博客](https://ouuan.github.io/300iq%E5%A5%94%E5%8C%97%E5%9D%A1/)了解到大概的注意事项，所以就在等候的时候写自我介绍。在手机上写了 900 多字，又请我妈提意见，删到了 700 多字，于是就被叫到门外等候了。 等候的时候把稿子读了两遍多，就进场了。 没想到的是自我介绍只有 $1\sim 2\mathrm{ min}$，我只好在说的时候自动删除内容。自我介绍的时候我还有一些紧张，不过强行调整过来了。 自我介绍完毕是面试官就自我介绍中的内容进行提问，居然问了“文化课成绩如何”、“你们学校多少人”、“每年多少个清华北大”之类的问题，之后就问了“你的嘤语怎么样”，自然过渡到嘤语阅读了？而且还要求出声朗读，感觉自己哑巴嘤语被发现了。文章里面大量出现 LBS(Location Based Services)，还有 privacy，根据嘤语老师教授的嘤语阅读技巧——画框架，我算是大概理解了文章的 structure。之后面试官问我“What’s the passage mainly about”（事实上，是用中文问的），我就抓住了这两个词。似乎面试官还比较满意？ 此后就问我开发的小程序的主要架构啊，还有我无意提到的 FFT 的原理啊什么的，感觉我回答得自己还算满意。接着计时器“嘀嘀嘀嘀”地响了，就顺势结束了。 感觉表现得还算满意吧，估计也是了解了大概流程的原因吧。 下午的宣讲居然没有讲题，差评。一开始的关于 THU 科研生活的宣讲还比较有收获，再次说明了我和强省学生在综合能力上的差距。后面的宣讲就显得主题不突出，十分催眠了。 据说今年发的纸非常多，那想必也是没有什么用的。 ### 休闲娱乐和后续 晚上去了一趟国图，TP 的书真的非常多（比数理化加起来的两倍还多），可能是因为这个阅览室是面向大众的吧。然后各种大学教材特别多，不禁让人怀疑是否应该留更多的空间给专著，毕竟各种教材的内容都基本相近嘛。 第二天没做什么，下午就回校了。早上还有幸看到了一次小雪，不过雪粒就像碎屑一样小，也没有特别壮观…… 一上文化课才知道，化学已经上到了“不认真学就会导致选修 4 完蛋”的化学平衡了，看来选 4 要完蛋了～（逃 ### 致谢 这次首先要感谢父母的陪伴，让我在 BJ 都方便了很多。 接着要感谢老师同学们的鼓励，让我更有信心。 最后还是给 Hanakiko~ 希望这篇流水帐一样的游记也能给今后去 THUWC/THUSC 的同学一点帮助吧。