PKUWC & WC 2025 游记

PKUWC

Day 1

早上 7:40 起床，爽睡了。

路上 wc 跟我说只有我没到了，仔细一问原来我听错集合时间了，这下爆蛋了。最后迟了大概 7 分钟才到。

报道完在边上随机游走，cyf 带着 zxx 来和 zyz 面基，我在旁边有点尴尬就偷偷润了。

在报道厅里面到了那老师和 Meatherm。还收到了 Mea 的徽章。大家都好帅啊。

开幕式没啥好说的。午饭还行，不是绍一食堂承包，应该没有卫生问题。

吃完饭回报告厅开了一会 Phigros，然后背了下板子，没记住。

进考场试机，配了下 VSCode。看眼试机题，怎么是我玉玉症题，skip。第二题不会做，懒得想了，默写了一下 NTT。

开始之后先看 T1，感觉不太会做。看眼 T2，数据结构。再看 T3，看着好眼熟，但是没啥想法。

继续做 T1，没啥想法，先猜了个 $a > b + 1$ 的结论，交上去发现假了，有点急。仔细想了一下，发现本质上是构造一个 $a + b$ 个点的图使得最大独立集只有 $a - 1$。

这数据范围铁 $O(T(a + b) + (a + b)^2)$ 吧，一直在考虑怎么 DP，发现不可做，而且怎么想也不会是 $O(T(a + b) + (a + b)^2)$ 的，倒是像 $O(T)$的。这个时候已经开急了。尝试考虑图能长啥样，突然意识到对于一个连通块其中每个点理应是对称的，然后再玩了一下别的环状的图发现都不如拆成若干个团，写了个 DP，发现没 WA。那这不是 $O(1)$ 的吗，交上去过了。司马题浪费我一个小时。

然后看 T2，考虑扫描线，考虑每个 $l \le v \le r$ 啥时候能产生贡献，要求不存在 $l \le u < v$ 使得 $depth_v - depth_{lca(u, v)} \ge x$，考虑 LNOI LCA 那个 trick，在每个点上维护其上次被覆盖的编号，然后对于每个点他的祖先就被分成了若干段。发现是颜色段均摊，这样就只有 $O(n\log n)$ 段了。然后写出限制，左端点的限制可以容斥掉，这样就是一个四维偏序。发现我只会写 bitset，看了眼数据范围，没分，玉玉了。又想了一会胡了个假做法，打算开写，突然发现对 $x$ 的两维限制也可以容斥掉，以为转化成了二维偏序，直接写了。

还没写多少发现假了，但是还是三维偏序，打算写完跑路。CDQ 分治写寄了，但还好每调多久就过样例了。交了一发，刷新了好几次还没出结果，先去上个厕所，祈祷能多拿点分，回来一看屏幕上怎么全是蓝的，再仔细一看发现真过了，最后一个包只跑了 3s。

此时还剩 1.5h 多一点，T3 只会三次做法，想了想平方发现不会，想了想 B 性质发现也不会，只能找到一些看起来没啥用的性质。很破防，只能先把三次方写了，交上去确实是 10 分，但是第二个包 WA 了，很问号。根据 PKUWC 传统数据强度猜想把 bug 修掉应该能过 sub2，但是看了很久没发现哪里有问题。重新看了眼题突然意识到可以绕一圈回到自己，改了改确实过了，20 分到手。

但是感觉只有大众分，继续思考，这个时候只打算思考 B 性质，发现对于每个点 $i$，如果答案不是其所有后继的最小颜色，那就是最小颜色 $+1$，那就只要 check 最小颜色能不能成为答案就好了。但是考虑第一步走到的点如果最小颜色和当前点相同那就要考虑次小颜色，然后又爆蛋了。想了很久不会，然后突然意识到在有 B 性质时走到的一定是这个颜色的最后的点（即不偏序其他同色点），那就不会有最小颜色相同的情况了。但是如果有环的话会在自己的强连通分量里绕，所以只能解决 A 性质。看了眼时间只剩 20min，光速开冲，光速过样例，交一发，WA 了，瞬间红温。急急急写对拍，拍了两组就出来了，调了调发现是把 $k$ 写成 $n$ 了，改完一交过 sub3 了。此时 $100 + 100 + 50$，感觉应该不会比别人低太多了，而且没啥时间了，就弃疗了。

但是还是先想想后面的分咋做吧，发现没有 A 性质时只要讨论一下强连通分量内的颜色就好了，然后再仔细一想发现好像没有 B 性质时也会走到这个颜色的最后的点（真的吗？应该没嘴假吧？），那好像不是啥很难想的东西，感觉大家应该都要 AK 了。

最后剩下 9min，写了个 SAM 以防明天要用。

出考场没看到熟人，在门口等了一会发现了喵仔牛奶，问他多少他说除了 T1 全打暴力。然后看到了牢张，问他 AK 没有，他说他 220，我说我 250。然后看到了 Fido_Puppy，他也是 220。

cyf 不出所料 AK 了，wc T2 没调出来。问了一圈好像 sxyz 除了 cyf 没有高于 220 的。

回家路上看了眼群，好像略高于大众分了，还算比较能接受的结果。

感觉这场打得很不在状态，T1 T3 都唐完了。做每个题的时候心态都很爆炸，现在想想如果我心态好一点说不定 T3 直接就过了。又是被心态影响严重的一集，下次能不能别再这样了……

那老师和 Mea 和 wc 好像都有点爆，希望他们明天能翻盘。

Day 2

早上 6:15，又一次由于忘关闹钟被吵醒了。

提前了 10 分钟起床，这次没有迟到。

dyh 询问分数，我说我 250，然后被旁边的 lanos 辱骂了。原因：

我寻思我光看名字里有 x 了，忘记看多少分了（bushi

上午讲座讲了 AI 和波特，感觉都挺有意思的，但是好像没学到啥东西。

吃完午饭去宿舍逛了一下，这也太豪华了吧，全方位吊打绍一了。这就是贵族学校吗。

看完之后回报告厅打了会 phigros，然后就收拾收拾去考场了。

开场看到 T1，是个交互，瞬间没绷住。读完题没啥想法，看眼 T2，感觉是阴间题。再看眼 T3，没啥想法，还是先做 T1 吧。

先考虑对着两个点把所有点都问一遍，看能知道啥，发现啥都不知道。然后考虑求树的直径的方法，感觉应该是找两遍最远点，想了下咋求最远的点，发现最好是能找到相邻的两个点，然后思考咋找，结果不会找。

又想了一下发现所有点问一遍后最远的点是叶子，然后叶子的父亲可以问，这样就 $2n \pm \varepsilon$ 找到两个相邻的点了，然后再所有点问一遍就找到了一个端点，然后一样的方法找另一个端点，这样有了个 $5n \pm \varepsilon$ 的做法，看了眼时间，怎么已经过去四十多分钟了，赶紧写完跑路吧。

写完没过样例，又调了调交上去 WA 了，急了。写了个拍子，调了一下，又 WA 了，交到第三发才对。测出来竟然有 83，不管了，下一题吧。

想了下 T2 发现每个位置应该先能拿 $k$ 个就拿 $k$ 个，之后就从前往后考虑然后考虑当前这位用不用操作 2 DP 就好了。诶那这不是做完了吗，哦不对状态还要记当前这位剩下几个。诶那不是只有 $O(n^2)$ 种状态，直接开写，然后只过了 $c = 1$。非常问号，又红温了，看了半天没看出问题，写个暴力，也 WA 了。改得再暴力一点，然后又 WA 了。交了好几发已经暴力得不能再暴力了，一直在想哪里考虑错了，没想到啥问题。试着把模 $k$ 删掉，然后过 sub1 了。

这个时候很懵，写了个拍子，然后玩了一下，发现得保留一个 $k$，然后改了改就 73 分了。

此时已经过去两个半小时，没啥时间了看 T3 吧，前两档好搞的，第四档应该分讨一下，先把前两档写了，没过样例，调了调发现是个唐 bug。然后 sub4 玩了玩发现不如直接写记搜。但是记搜好像只能每次根号求因数啊，算了写了再说，写完又 WA 了，调了调发现还是之前那个唐 bug。交上去直接过 sub4 了。

后面不会了，算了下分，$83 + 73 + 36 = 192$，那我很需要 T3 的 sub3 的八分啊，想想咋做吧，诶等会这不直接狄利克雷前缀和吗，然后又写挂了调了一会才调好。只剩下半个小时了，刚好 200 分，有点爆蛋。

后面半个小时一直在 T1 T2 T3 之间来回跳动，三线开题，但主要 T1，胡了好几个 $4n \pm \varepsilon$ 的，有些还是假的，但是都没啥用。

最后五分钟放弃思考了，看着时间一点点跳动到 17:00，很破防，想哭但是哭不出来。结束后出场都不敢听旁边别人讨论，很怕 T1 是个傻题然后只有我没过。

到场外之后看到 wc，询问战况，发现他也没过题，然后看到 zyz 和 fhq，也说没过题，问了一下好像都没到 200。lanos 200，tx 和 pi 没上两位数，太吓人。

问了一圈发现其实没有那么爆，这下放心了。

紊莫出场说 T1 没调出来，wc 问他有没有判 $n <= 2$，他：啊？还有 $n = 1$？不禁回想起三天前模拟赛所有人 T1 都由于没考虑 $v = 0$ FST 了，这波模拟赛白打了属于是。

可能还有点想说的话，但是现在忘了，想起来了再补（