THUWC2025 游记

· · 生活·游记

不要问我为什么没有 WC2025 游记。

Day 0

报道日，没干什么有意义的事，连摆的欲望都没有。

因为飞机很晚才到北京导致我 4 点才出发，进校门就看到巨长队列。并且很遗憾地成为了队尾。

面到了 @shunpower 和 @stayalone，不过都是老熟人了。

但是在大厅内排队的时候被神秘老师带领我们队尾的一群人从反方向排队，成功比早到一个小时的同学早签到！

Day 1

T1 发现是送分的线段树优化 dp，8:30 切了。

T2 在二维情况下是典题，考虑三维情况。这种题比较经典的方法是利用点线面去掉所有不可能有贡献的点，但是我采用了一个很好写的偷鸡做法：

考虑对于目前所有的点集建一颗树，每次从点集中选出一个最大值，然后把其它的点根据是否与它的 x 或 y 或 z 不同塞进它的三个子树（如果有多维不同，则每个子树都得塞）。

这样建出来的树大小是 3^4 - 1 级别的，考虑优化。

发现一个若一个子树已经是有 x 不同的边了，则它不需要再延伸出 x 不同的子树。

于是我们把子树大小优化到 n! 级别了，实际大小是 16。

此时你直接每次暴力查询和暴力重构就可做到 O(16^2n) 了，加上卡常可以通过。

其实还可以使用定期重构把复杂度变成 O(16n)，考场上没试过。

码码码，9:40 过了。

T3 有点意思。斜率的单调性显然，可以打表验证。

最后的每个球有 3 贡献有点麻烦，考虑在加入球的时候就加上 3 贡献，然后给前两个操作都减去 3 贡献就好了。

然后我们不难注意到一个性质：每次改变上界，增加的一操作贡献数量和减少的二操作贡献数量 a-b \le 1，理性证明较难，可以画折线图理解峰与谷的关系。

考虑将上界从无限向下降。根据上述性质以及斜率的单调性，我们可以注意到二操作的数量一定不能减少。

也就是说，答案的峰顶就是二操作的数量最大时候的最小上界。

考虑此时答案的组成：

  1. 每个球有 3 的贡献，好算。
  2. 每个成功的二操作有 13 的贡献，类似括号匹配的方法即可。
  3. 在取到最小上界时候的每个失败的一操作有 5 的贡献，我们考虑这个怎么算。

由于一操作和二操作都随着上界不降或不升的，我们发现一操作最终的贡献是一段连续的 1。

开始存在贡献的位置显然就是折线图的最高峰，就看最小上界在何处取得。

手玩折线图可以发现这个上界的值就是，对于每个峰谷，它前面的最高峰减去这个谷的深度，对于所有的峰谷的最大值。

形象的理解可以用括号匹配的思路，不过我不会就不说了。

12:57 提交，过拍了应该没出锅。

T4 不会，就捞 10 分跑路。

Day 2

面到了 @Jorisy。

声明：我有一等，不要模仿。

屎中屎。看不懂出题人在说什么。

生气了，发现 Linux 的字符里有麻将牌，于是开始自己写麻将。

写了 3h，成功实现了各种役满判定和类似青云之志的换牌和摸牌，爽了。

最后只拿了 Ag，意料之中情理之中。

怎么还有 rk20 的榜，早知道不摆了。