PKUWC2025 游记

早上 PKU 的老师说了一些非常好的话，可惜我没听在看 @NULL1F1CAT10N 巨佬打 phi。Disorted Fate IN 不给人打，但是这个巨佬硬抗底力段，令人感到震惊。

~~这里先声明一下我是 phi 菜鸡~~

然后老师宣布可以去吃午饭了。/oh 但是我们几个作为全场最缺失大脑的几个人成功走出了最长路，使人感到气愤。/ll 然后就是排菜排了半个小时。在打饭时我比较有素质去排了队，然后又排了十几分钟，令人感到抽象。

然后试机。yeah！然后发现电脑开不开。

后面花了十几分钟开机 /fn 发现只见过试机 T1 没见过 T2 应该是 PKUWC2022，有点久远。

试机连着正赛。等了 10min 后正赛开始 /oh

开 T1，欸我不会。手膜样例不可做，但是想了一下后发现为了尽量少试，分成若干组使得至少一组有两个好的，然后每组之间两两试一遍。

好像是对的，写写写，过过过。

然后开 T2.完了 DS 我不会啊。先把 1e4 的点写了，过过过。

然后开始思考 l = 1。发现只用维护每个点在往上跳几层时会和编号小于自己的合并在一起。然后树剖 + 线段树 + 二分 + 扫描线做即可。

写写写，过过过。

然后剩下的我也不会了/ll 只能开 T3。花了一些时间读懂题，然后发现涉及有向图连通性问题，完了不会啊 /fad

然后只能写一个 \dfrac{n^3}{\omega} 的抽象复杂度，能过 20pts /fad

然后不会了，去玩俄罗斯方块了 /kk

100 + 41 + 20 = 161 菜爆了

好的早上也没怎么听就去看 @NULL1F1CAT10N 巨佬打 phi 了。打出 94 万多分，恐怖 /fad

然后去吃饭，好的继续看 @NULL1F1CAT10N 巨佬打 phi。然后他在一首 AT15.9 的歌中连了全曲的 > 80\%。mol 爆。

然后速通到考场。然后又研究了半天如何开机，最后发现一按就开只是要等一下 /gg

发现 Day1 的代码没删 ~~欸早知道我多打点 ds 的板子了~~

开 T1，好的是交互。调了一会儿把 n \le 100 写了。想到自己菜的无语而且在某些比赛中不会交互险些阿克所以先把交互跳了。

开 T3，然后发现是抽象数学计数问题。先把 Bn \log n 写了，发现过不了 5e6/fn，然后这个时候我选择先写 l = r 的倒着 dfs。

但是我神秘的打错了然后能过 5e6？！然后改了一下过了 l = r，拿到 44pts。

再开 T2，感到十分神秘，然后打了贪心的 c = 1。再想了一会儿想出了一个 \dfrac{n^4}c 的 dp，c 是一个巨大的常数。写写写，过过过。

然后想到可以倒着扫并使用警报器算法优化成 n^2 \log n。然后就写了，但是不过。打了一个拍子和原来的代码拍，调出了几个错后还是不过。想着没什么时间了就先跳了。只拿了 49pts。

最后开 T1。思考了一下直径正常怎么求，然后就写了一个求距离自己最远的点的代码，有 \dfrac{1}{n} 的碰撞概率，就把 n \le 100 的代码拼了上去。这样是 8n 的。拿到 41pts。

稍微思考后修改成了 6n 的，变成 56pts。此时只剩下 5min。/jy

然后后面 5min 想不出来了，遗憾离场。

56 + 49 + 44 = 149.