THUWC 2025 游记

· · 生活·游记

省流： 别样的排队大战。

Day 0

报道日，排队 2h。

别人都在试机，而我在做题。

T1 a+b problem 5 分钟才写完。

T2 k 子棋构造平局暴力打了 25 分钟。

T3 猜测三个升序序列中的第 k 小值，每次可以查询某一序列的某一位置的值。

先花 10 分钟打了 3k 次数的暴力，再花 15 分钟想了想两个序列的 log 做法，最后三个序列化归为子问题想了 10 分钟双 log 做法。然而不会 3 倍 log，但有一个显然的结论是：若三个位置相加 \ge k，那么值最大的位置的后面一定不是答案，据此可以缩小范围。

用时太长被喊了出来，心想手速这么慢明天和后天打不完了。

Day 1

考试日，食堂排队 1h。

技巧忘光了。

T1 dp 题，T2 DS 题，T3 性质题，T4 神秘结论题。

T1 意为构造一个排列，有 m 条限制，每条限制形如让区间 [l,r] 的数递增或递减，要求构造的排列满足最多限制数。

看到 T1 赶快写搜索和所有区间不交的特殊性质，1h 时还只有 34 分。我总不能对着排列设状态吧，因此经过仔细推敲对特殊性质和判断函数的观察，决定用记录差分正负的数组设计状态再构造出一个排列。这样一来，dp 很简单，因为每个位置只有正负两种情况；构造也很简单，因为只要让前缀的值域连续，在值域两边添加数，最后平移值域至 [1,n] 范围内就行了。

dp 就是经典的线段树优化。写完已经过去 1 小时 40 分钟。

T2 求与当前点每一维都不相等的点的最大权值，看一眼觉得 k-d tree 能写，但写完不加优化的 k-d tree 才发现只有 6 分，改为带修 k-d tree 还是 6 分，很奇怪。经过 1 个多小时后才发现最优化剪枝没加，加之后能过正常的 n \le 10^5 的点，但 1 秒的时限还是太卡了。又花 1h 想尽各种优化未果，写了 C 的特殊性质，即只求个数，发现容斥常数极大，遂只敲了其中一维 \le 2 的部分分，实在不想打了，于是止步 55 pts。

T3 打了 5 pts 暴力。

T4 打了 20 pts 暴力，在只剩 40 分钟时连忙敲了 10 pts 压位高精。

手速实在是太慢了，大脑也跟不上，于是只有 100+55+5+30=190 了。

出来一看，Monomial 四题暴力拼包拼完了还是比我高一分，发觉自己 T2 特殊性质没打全，T3 完全没打特殊性质。算了，拿奖就行。

下午参观清华“自强”科技楼，先去负一层，人挤进来了，于是到不了其他层了，于是先回了，早了半小时放学，晚上去逛商场，买了若干新衣。

Day 2

工程场。

每题 10 分钟迅速切了前三题，T4 ffn 写了 1h 但怎么卡都 TLE，不管了开 T5，然后就卡在了 T6，最后又卡了卡 T4，未果。然而发现 T6 有部分分，于是最后 2 分钟交了空函数上去喜提 8.64 pts，当然这也是很多人细节写错的分数。

大众分 508，而我被卡掉了 25 pts，不知道为什么。下次一定 AK 工程场。

下午听讲座，很困，但一些地方还是有笑点的。人工智能只能拥有人类发明创造的东西，但不可能有生物进化的技能。

颁奖，银奖，大概是三等约，没什么用，被 Monomial 吊着打。

羡慕金牌爷。

Day 3

回家。