PKUWC 2025 游记

· · 生活·游记

PKUWC Day 1(2025.1.14)

首先进了考场，同学 zgc(@cancan123456) 刚好坐对面（雾

试机赛 T1 不会，T2 写了 60 就跑了，然后 zgc & gyf 给我锐评了一下 T1 并说了一下 T1 做法。

然后罚坐二十分钟之后开题，T1 是个啥，怎么一点不会啊？？？？T2 怎么是数据结构题？？？？T3 怎么是博弈？？？？题面还搞这么复杂？？？

算了先找 T1 性质，思考了片刻发现 a > b + 1 是简单的，交上去获得了 5 分，然后写了一个理论上界上去，只过了 a = 2，狂砍 10 分。

然后给 T1 写了几个上界取 min 都错完了，写了 dp 也似了，暴力匹配也似了，不是哥们？？？？？这样下去肯定不行了，于是去做 T2。

T2 n \leq 10^4 可以直接暴力，枚举一下 x，这样可以 O(n^2)，写了获得了 24 分，然后想了若干个莫队的假做法，感觉 l = 1 的 17 分可以思考一下，这个就是求每个点的最小满足条件的值，但是这样做不了，思考一番发现可以考虑去重，每个点产生贡献的 x 值是一个区间，然后就可以离线 + 二维数点做了，通过之后获得了 41 分。

看看 T3，发现有一个裸 O(n^3) DP，写了，只过了 Sub1，但是 Sub2 怎么没 T，但是 wa 了？？？我过了 Sub1 啊，一番查错之后发现一个点可以通过环再转移回去，加上了之后就通过了 Sub2，然后再回去做 T1。

考虑刻画一下这个最劣情况，发现可以转化为图论染色可行性的题，写了一个爆搜把 n, m \leq 4 过了，然后打了一个表，发现了 a = 3 的答案差分大概是 2\ 2\ 3\ 3\ 4\dots 这样的，感觉有点东西，写了之后通过了 a = 3！

此时已经有了 30 + 41 + 20 = 91 分，肯定不够。

看一下吧，a = 4 好像也有点类似的规律，只不过把 2 都换成 a - 1，改改改交上去.....，它通过了？？？？？？？？？？！

这么牛逼啊？？？？？？此时是 3h15min。

加下来尝试冲 T2 莫队，全错了，冲 T3 的 Sub3 也未果，只能遗憾离场了。

问了一下自己是个大众分（有可能还小于大众分哦哦哦），同学分别获得了 $161/177/200$ 的分数，拿了米 $161$，pcf $168$，好家伙我垫底了是吧，Day 2 要加把劲啊。。。。 怎么一堆 $220+$ 啊，zxx $300$ 也太牛了。 ## PKUWC Day 2(2025.1.15) 上午复习了一下 NTT/FWT，期待下午的计数题。 快进到 13:00，开题，T1 怎么是交互，T2 题面好短，感觉挺像 flows 的，T3 有 $998244353$！ 怎么三题一题不会啊，T1 一分不会，寄，T2 只会 $c = 1$，T3 也只会裸暴力。 先把 T2 $c = 1$ 写了，得到了 $11$ 分，然后就不会了，Sub1 都不会，然后给 T3 写了 $O(Bn \log n)$ 的暴力，只过了 $24$ 分，想到了猫猫昨天在 u 群说 pragma，像云浅一样发了一个： ### 可以用 #pragma 吗？/kel #### 如题。 马上得到了回复可以，那不是无敌了？然后加了一个发现还是 $24$，唐。。。。。。 然后枚举 $B \leq 4$ 的情况，枚举了一半要吐了就直接写了个 DFS，就通过了 $36$ 分，给 Sub3 各种卡常也无法战胜，用时停在了 14s，似。 思考了一下 T2 的 $c = 1$ 的策略，胡出了一个 $O(na^2 \log n)$ 的 DP，写写写就过了 Sub1，此时手头有 $0 + 28 + 36 = 64$ 分了，但是根本不够啊？？？ 回去搞 T1，观察之后发现了如下结论： - 可以 $n - 2$ 次查询求出两点的距离（但是会把距离为 $1$ 判成距离为 $2$）。 - `query(u, v, w)` 返回的是 $u, v, w$ 构成的虚树大小 * 2。 - 可以维护虚树大小最大的三元组 $(u, v, w)$，答案应该就是在这里面取的。 然后写了一个 $O(n^3)$ 的裸暴力，没调交上去过了 $16$ 分，现在总分有 $80$ 了。 然后上了个 WC 回来发现可以像动态维护直径一样维护三元组，这样就可以维护出直径可能的位置了，赶紧写写写，次数也懒得算了，应该能过一些分，自测，，，啊？？？wa？？？ 发现是自己一个很唐的地方写错了，改了之后过了一个手造的树，把树加强了一下也过了，没时间想了赶紧交！ 很紧张，不停的 F5，差不多 40s 等出来了结果，$56$！！！赶紧又去了个 WC，现在有 120pts 了，努力卡卡 T1。 我的次数是严格 $6n$ 的，卡的还挺满，尝试用虚树大小省掉 $n$ 次查询，但交上去全错了。 发现 $dis = 1$ 就似了，此时我想到交互库不自适应，那是不是可以思考一些非确定性做法呢，把求 dis 的地方加了一个随机，改了一些参数交了好几发，都是不同的参数，然后在主页面不断刷新，看到自己的 T1 从 $56 \to 70 \to 83 \to 89 \to 95$！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ 赢！！！翻盘！！！！ 然后给维护三元组也加了随机化，也最高只能过到 $95$ 了，下班。 $95 + 28 + 36 = 159$。 出场问了一圈好像这个分还不错，pcf $188$ 还狗叫要退役了，pcf 真的是。。。。 总分 $161 + 159 = 320$，2= 肯定有了，看看 1= 有没有。