THUWC 2024 游记

Day 0

报道日。上午在重庆随机游走，感觉需要一个三维的导航。上午 1789 在群里说要来重庆参加第五人格大赛，我认为他在魔怔（埋下伏笔）。

下午报道，在门口遇到了超超和 yzy，但是他们报的都是 pkuwc，~~所以是来 NTR 吗~~。进去报道，面到了空跌，然后空跌去试机了，我又遇到了超超和 yzy。我们发现 1789 在群里说看见我们了？然后我们也看到了 1789，原来他作为高三 C 类选手也来参加了 thuwc！我们就一直在和他魔怔说“你凭什么能来啊？你凭什么能来啊？”突然回忆起去年 thusc qzy 魔怔 1789“你凭什么能拿到约啊？”这下形成闭环了。聊了会天就下去试机了，发现没什么好试机的东西，正好遇到了 zhk 就和他一起走了。然后就回宾馆开摆了。

Day1

进场发现电脑坏了，首绷。昨天还没有坏的。找 zyb 换了一台电脑。开题，发现 T1 $O(2^nnm)$ 好做的，然后就写完了，测了一下本地速度 0.6s 很对啊，交上去 77 分。然后卡了卡常变成了 90 分。但是本地是 i3 啊，评测机在玩原神吗？不管了先看看 T2，70 分直接矩阵快速幂就行了，写一下过了 70。回头看 T1 发现可以预处理选每个集合的最大收益然后子集卷积做到 $O(2^nm+3^n)$，写了一下果然过了。

这时候大概是九点多一点，看 T3，交互题，前两个包的 24 分是送的，先写了。写完就会了一个操作次数 $2n$，$\sum=n^2$ 的做法，大概就是找个指针从下往上扫一遍，写了一下交上去有 49 分。又想了半小时左右想出来了一个分块做法，查询每一块有没有东西，然后只有两条对角线是有用的，写了一下卡了卡块长获得了 68 分。基于这个分块做法的分治做法貌似复杂度上没啥前途，就去看 T4 了。

十点半左右写完了 T4 的 15 分暴力。然后想了想会了 T4 的第二个包，大概就是这是个图，求最大的 $c$ 就是建出最大生成树查链上最小值，也就是 kruskal 重构树，写了 4.5k 代码调了一会过了 36 分。这时候大概不到十二点。

想了一会发现 T2 的矩阵快速幂矩阵满足 $|x-y|$ 相同的位置值相同，然后就可以 $O(n^2)$ 做矩阵乘法，推了推细节就开始写，写完第一发还 T 了，卡了卡常数才过 90 分。同时发现 100 分就是 NTT 优化卷积，但是谁会默写 NTT 呢？罚坐 20min，最后是 100+90+68+36=294，除了卡常应该没有挂分点。

问 whk 有没有过 300，他说过了，太强大了！他写了 NTT，然后写了 T3 我认为没前途的分治做法并加了牛逼剪枝过了 75 分。很厉害！问了一下沙东的其他人没有过 250 的，除了 1789，原来退役半年的高三选手也这么牛的！

下午看群发现很多人 T3 过了 97，怎么过的呢？貌似是那个分治做法如果右下角有就只保留右下角，但是这不是纯纯假做法吗？在 u 群里也被 hack 了，希望出题人 system test 能卡掉。

遇到了 lmt，原来他没有去 p 而是又去了一次 t。和他聊了几句，然后去听了一个没用的讲座。

Day2

由于 Day1 有一定优势，Day2 的策略变成了求稳。但是接下来你会看见我这个策略怎么碎的稀烂的。

开题。四子棋？对抗博弈？这种题材还是有过一点了解的。花了半个多小时读了读 ppt。看懂了极大极小，ab剪枝，蒙特卡洛。信心上线不知道怎么写，但是为了求稳，写前面的就够了。

写并调了 1.5h 大概过了第一个包，第二个包 80 分。大概是一个搜几层然后随机几次用胜利次数作为估价函数，没交后面的，加了点剪枝给第二个包过了 90 分。然后做了一个错误决定，我认为第二个包一定是要过的，于是卡常，卡了半天常数和参数还是 90 分。突然回想起来五个题只能交 10 次！发现我还有两次提交还有三个包没交？？当时心跳骤停。只能交了三四两个包分别获得了 80 分提前 1h 结束了今天的比赛。喜提 100+90+80+80+0=350 分。剩下的 1h 心里一片空白，充斥着会因为最后一个包的 40 分没拿到拿不了 1= 的担忧，以及 IOI 赛制挂 about 40 分的后悔和遗憾。

赛后问了问其他人，350 好像算高分？但是还是有 380 左右的，所以没有这 40 分还是输。有了这 40 分大概就是很高的分了，现在就是一个不高不低的得分位置，全错了。有不少人比较寄，就不太好意思细问了。

下午听报告见到了航爸，聊了几句。最后领了个一等约，但是还是错完了。