THUWC2025 游记

· · 生活·游记

Day 0

来的比较早，没有罚站，很快签完了到。

你说得对，但是为啥 rdfz 两顿午餐卖我 100 RMB 啊？？

第一次 ak 试机赛！

晚上挺早就睡了。

Day 1

去麦吃了早饭。

开 t1，想了一段时间二分图匹配/模拟费用流相关，想了一段时间决策单调性相关，最后发现我是啥比，1.5h 通过了。

开 t2，一眼想到了最大次大相关，想了一段时间去维护一个神秘数据结构（大概胡了一个高度为 3 的 3 叉树去解决这个东西），发现没啥道理；然后想能不能线段树分治之类的，感觉又没啥道理。

这时候大概想了这样子的一个东西：

对于一个前缀 [1,i]，我宣称一个 j\le i 是有用的，当且仅当存在三元组 (x',y',z') 使得其和所有 k\le i 且 w_k>w_j 的 (x,y,z,w)_k 均冲突，且其和 (x,y,z,w)_j 不冲突。

并且很容易注意到，有用的 j 不是很多，只有 \mathcal{O}(1) 个（应当是 \le 8 个？），下面记作 m。

且若 j 对于前缀 [1,i] 无用，则对于前缀 [1,k],k>i 也都无用（因为限制只会更严）。

那我就时刻维护所有有用的 j 构成的集合，每次新加入一个 i 暴力拍扁重构就好了，复杂度大概是 \mathcal{O}(nm^3) 或 \mathcal{O}(nm^4)，常数很小且跑不满。

乱写了一通，通过小样利一交就 800ms 通过了。

其实这个题过得还挺快的，但记不清具体时间了。

然后开 t3，发现我怎么只会第一个包啊？？冷静了一下，手摸了 k\to k-1 的影响，发现 [ans_{k-1}>ans_k] 这个东西有单调性，好的我会 \mathcal{O}(qn\log{n}) 了，先写了一下拿下 24 分。

又去把 t4 20 分写了，想用 long double 把 30 冲过去，但好像并不可能。

继续回来分析 t3，想了一下发现我要是能求出 k 后面算贡献乱分讨一下就做完了，但我求 k 怎么只会单次 n\log{n} 啊？？

想了一堆可能很有道理的东西，但写了一个我觉得没啥道理的 \mathcal{O}(n) 求 k 的东西（伏笔），把 36 分过了，继续尝试分析无果。

最终 100+100+36+20=256，是不是这个分还可以来着。

出来问了几个人发现没有比我高的。

xhgua xuzishuai 和一堆人的 t2 8n\log{n} 做法全部被卡常了，what can i say。

下午 合照 & 嘉年华 都在罚站。

伏笔：在 Day 2 颁完奖后 xhgua 跟我说 k 差不多是个最大子段和，冷静思考了一下：我那个 \mathcal{O}(n) 代码写的咋是 \max\limits_{1\le i\le n}(pre_i-\min\limits_{j\ge i} pre_j) 啊？？我咋没看出来这个是最大子段和啊？？

不过感觉当时看出来也没时间了，最后那个 36 分代码差不多也是最后 10 分钟交的了。

Day 2

又去麦吃了早饭。

开场发现工程题又是 AI 相关/tuu

不是哥们，怎么函数式交互并且还没有下发样例的，这是肉眼静态查错顶针大赛吗？？？

迅速通过了 t1，t2 二维矩阵转一维比较魔怔，挂了一发。

一开始没看懂 t3 在说啥，交了几分获得 0 分。

这时候去看 t4 然后把他过了，再回头看 t3 突然看懂了也过了。

然后做 t5，CE 了几发然后过了。

这时候可能 2h 不到一点。然后看 t6 没看懂在说啥，这时候记错时间以为只有 1h 了，不过后来监考人报时发现看记时间了/hsh

t6 仍然看得云里雾里，又过了 30min 终于捋顺了，写了 30min 写完了，CE 了若干发在大概还剩 40min 多一点时终于获得了非 CE 的成绩，获得了 8.? 分。

然后随机调参，获得过 3.?,6.?,8.?,9.?,20.?,28.?，最终没调出来，获得了 28.?。

最终 100+100+100+100+100+28.?+0。

两天总分是 256+528.?。

出来遇到 xhgua ak 了，其余人都是 500+a(a<10)。

遇到教练，教练说现在改为一二等合并作金牌，三等作银牌。

然后就 Au 了，看起来报名字的时候是按成绩降序报的，我似乎是金牌第二组靠前的，加上卓越奖 20 个应当 \le 40 名？

xhgua 似乎是 29 名。

感觉最后那个 t6 调出来就有卓越了啊，有点可惜。

其余人都是 Ag 了。