THUWC 游记

nb_jzy · 2025-01-17 15:17:35 · 生活·游记

Day 0

第一次自己坐飞机。（很小的时候坐过几次飞机）十分激动，拍了很多照片，感觉起飞和降落的时候十分有趣。天空的景色很不错。前面是 @zhuzc，旁边是 @liduoduo2021，后面是 @nk_fzx_sd ，其他人也差不多在附近。

入住酒店，第一次见到暖气片，和 @liduoduo2021 一间房。

中午吃的吉野家（没听说过），然后去报道，搞笑的是一堆人在排队，我们从两点排到了三点过后。

更Joker 的是，我一开始并没有找到科技南楼，看到地标上只有三栋建筑，于是跟着走，结果发现迷路了。一路上问了一堆同学，才发现科技南楼就是我们进来的地方。。。

然后试机发现 VScode 并不能编译运行，也下不了扩展。于是我们直接掏出 codeblocks，不过还是不会在那个 X 开头的东西复制粘贴。所以直接在终端输出命令。发现题目除了 a+b，其他题目都不是很水，于是在想 C 题如何优化的过程中就到了 16:00，接着回了酒店。

晚上和 @nk_fzx_sd @i_love_xqh @zhuzc 一起玩耍，被一会儿玩 Hollow Knight，被苍蝇打死了很多次；然后 @zhuzc 让我玩了一会儿 Broforce。

接着就和楼下的大佬一起玩狼人杀和阿瓦隆，十分费脑子，22：00 后上去洗漱，23：00 左右睡了。

Day 1

0 分遗憾离场了。

和 @liduoduo2021，@zhuzc 在一栋楼，ljy 竟然和我在一个考室，并且我试机的时候根本没有看见他，比较的 Joker。然后 zzc 祝福了我们，就进了考场。

开场依然是通读全文，A 题很快就有了大致思路，看起来是构造，其实就是 dp 之后输出方案，并且这一看就是线段树优化。B 题直觉告诉我要将最大值转换为计数，计数就是一个比较简单的容斥。C,D 题没有任何思路。都只会最简单的暴力分。

于是准备先把 A 题搞出来，发现虽然思路比较简单，但是输出方案好像比较麻烦，因为上升和下降的一段会有交点，于是先不管了。"快速"打完了前面的 dp 部分，然后就发现过去了 1h。

接着想了一会儿方案怎么输出，先试了一种写法，调了一会儿过了样例，结果 WA 0 了。经过一些调试，过掉了一组手造的 HACK 数据，还是 WA 0 了。于是写了一个 \mathcal O(n!\times m) 交上去，然后开始对拍，发现最优值有的和暴力不一样，于是发现线段树上修改节点不能 +=，这样会算重贡献，所以改成了 =，对拍了 10000 组之后，过掉了。用时 1h50min。

然后 B 题想到了线段树上二分，是 \mathcal O(7\times n\times \log n)。正准备开始写，发现一个严重的问题，就是空间爆了。并且目测哈希表肯定不能估计成 \mathcal O(1)。然后想了很多办法优化，结果发现都不太行。于是就一直思考。然后准备写一个 \mathcal O(7\times n\times \log^2 n) 的书套数，结果写了很久，交上去喜提 6pts，不如 \mathcal O(n^2) 的暴力，关键是基本上全 TLE 了，还有一个 WA！

发现只有两个小时不到了。赶紧看了看后面的题。C 题思考了一会儿还是不太会，关键是 k 的取值是 1\sim n 的，每个都带进去算不是很现实。于是先把 D 题的 \mathcal O(n^3) 写了，发现只有 20pts，另外 10pts 还要写高精，感觉性价比不高，于是就写了 20pts，结果还弱智的写了将近半个小时。