WC 2023 游记

Ecrade_ · 2023-01-19 00:18:15 · 个人记录

前几天听课的我：看第一题，想题，想不出，听讲解，看第二题，想题，想不出，听讲解，看第三题，想题，想不出，进入梦乡……这就是传说中的冬眠营吗？

浑浑噩噩来到了考试日。

8:10 被通知考试延迟半小时开始，没啥精神的我为了保持清醒刷了会儿 B 站，结果越刷越困。

9:00 考试开始，下载了一年的压缩包。开题，第一题的区间修改和撤销操作明示要用个可持久化数据结构来维护，但 “ q 是 p 的因子 ” 这条限制一时没想到有啥用，就先弃了。

9:10 看第二题。题面异常简洁，一眼不可做，想了会儿无果后也先弃了。

9:20 看第三题。和去年一样是个交互题。题意很简洁，但感觉起来比第二题可做不少，就决定先思考第三题。

9:30 在草稿纸上推了会儿性质 A 的部分分，得出了个最劣时间复杂度 O(n^2) 的解法，不过由于边权随机，它的期望复杂度是 O(n\log n) 的（实际上如果数据不随机也可以一开始就给它打乱）。码完之后开始测样例，结果弹出个 Invalid output!，研究了下原因，发现是示例代码里的 vector 大小开小了，真有你的。改了之后顺利通过了样例二和样例五，但是过不去手造的 n=5\times 10^5 的数据。把次数限制调大后发现需要进行约两倍于限制的操作，看了眼代码没啥优化的余地后就去思考性质 B 了。

10:30 沿用性质 A 的思路，容易得到一个时间复杂度与结点儿子个数有关的算法，具体复杂度很玄学。很幸运，没调试几次后便通过了样例三和样例四。此时我进行了一个令人窒息的操作——下意识地以为这种算法过不去 n 更大的点，剩下俩现成的样例竟然都没测，而且其余数据点我也并没有在代码里囊括进去，直接输出了个随机排列（不过还好，后来测了下其余点是过不去的，但情急之下还是不能乱了阵脚）。拍了几个手造的随机树后我便直接跑去看前两题了。

11:15 开始思考第二题。原问题可以转化为在一张完全图上求一个哈密顿回路，使得相邻有色边颜色不同，但想了会儿发现这个转化其实一点用都没有。

12:00 思考了许久无果之后猛然发现只剩下两个小时了，感觉有些不对劲，如果再不开第一题很可能会寄，于是赶紧写完 m=1 的部分分就去看第一题了。但是第一题想了会儿仍然没想出来这个因数限制到底有啥用，便只好先把暴力写掉。写完之后发现没给 checker，为了节约时间便手动构造了几个小数据，肉眼查错。

13:00 不知不觉间只剩下一个小时了，但我仍旧没有任何进展。进行了一番思想斗争之后，我决定开始码性质 A 的部分分。

13:20 码完，没写 checker 的我只好用之前那几个小数据手动查错，看起来没啥问题之后便赶紧回去看第二题。先把暴力写了，但是连第二个样例的 n\le 15 的一百多个点都得跑个十几秒，很难受，于是直接开始想正解。在手推了几个小数据之后，发现可以将原问题抽象成：给定一堆点，要求确定一个点的圆排列使得相邻三点不共线。接着我就开始思考是否可以直接贪心，想了一会儿后突然意识到：我没时间了啊！想这么多思路，能实现得了么？很蓝的啦！有这时间还不如检查检查其它两题。

14:00 考试结束，交卷。

预计得分：35+24+56=115。

考完之后人很久没缓过神来，想着这次总分比去年还低，要是每题再挂个十几分连三位数都保不住，而且之前的分数线基本上都是金银铜依次 150,100,50 分左右，难道我要打铜了？

晚上听讲评，第一题听到了那步转换之后人都傻了，考场上完全没有想到要去转化贡献，还是技不如人了。第二题出题人首先搬出来了一道题，说考试的那题是由这题演化而来的，我仔细一看，这不是我之前模拟赛里切掉过的构造么？这两题都是调整法 + 构造，但是考场上根本没往这个思路去想。接着出题人又讲述了解题过程，抽象成直线的那步转化考场上虽然想到了，但也就止步于此了，还是缺乏一定的创造力。第三题大家似乎都没太听懂，大致思路应该是将树剖分成若干条链，然后用一种类似 \log 分块 + 分治的算法做到线性，听起来很神，不理解出题人是如何想到的。

到了第二天的颁奖仪式，开场表演之后便开始宣布获奖名单了。先报了下分数线，金银铜依次是 89,56,24，给了我些希望。依旧是那个熟悉的 PPT 背景，依旧是那个按分数从低往高报的形式，依旧是那个异常紧张的氛围。随着一个个名字被念出，随着一页页幻灯片被翻过，复杂的心理带来的压迫感使我度秒如年。在苦苦煎熬了六百多年之后，终于在榜上看到了我的名字。127 分，反向挂了 12 分，大概率是第二题暴力又水到了一些分。

第一次拿金牌（虽然没啥用），有些激动，故写下了这篇游记。

UPD:

实际得分：35+36+56=127。