PKUWC 2025

· · 生活·游记

省流： 100+41+20+41+73+44 = 319.

省流：考场开题跑路大神。

时隔半年写下又一篇游记。

求求你 PKU 能不能给我发个一等奖。

Day -114514

NOIP 考了 eps 分，打算滚回去考期末考试了。

Day -10

发现自己两个营都过了，于是复活了。

数学考试考了 100 昏。

Day 1

中午在食堂排了二十几分钟的队伍，急眼了。

下午开考，先看 T1，感受到要么是神秘递归到子问题的题要么是 adhoc 题。然后看 T2，怎么是数据结构题？然后看 T3，怎么是博弈题？然后感觉有点不妙了。

先做了 T1，一开始先尝试了若干种做法都只能通过 10 分，然后用手玩了一下 sub1，发现 a = b = 4 的情况分成 2,2,3 分别求解就只需要 7 步，然后就把 sub1 过了。然后我联想到应该可以考虑分成 a-1 组，每一组里面尽量平均的放东西。然后猜了一发就过题了。

这时候过去 40 分钟，然后看 T2，一开始看了很久没有一点点想法，我决定先跑路看 T3，发现 T3 20 分是弱智，然后我一开始把性质 A 看成了 a_i = i，然后我思考了一下只需要缩点在 dag 上做 O(b-a) 的查询 a 和 b 可达性的东西好像就过了，然后我觉得这个题是弱智？？接下来又想了很久，发现最后一个 sub 很困难，结果发现看错题条件了，倒闭。接下来开始写 O(n^2) 的暴力，发现太难写了，于是写 O(\dfrac{n^3}{w})。写了很久，然后一直 WA。

然后只剩下了一个半小时，赶紧跑路去看了 T2。好在我 T2 忽然想到可以莫队维护，然后发现了性质就是只需要维护相同深度 dfn 排序后的结果，瓶颈是动态查集合前驱后继，然后我觉得我牛完了，然后认为这个题正解是莫队卡常，于是直接上了 set 然后开写了，写的时候写了很多低级错误出来，在剩下半小时的时候写过了，但是只能过 41 分。尝试卡常，但是似乎完全没用。然后又滚回去看 T3，一眼就看出来哪里写挂了，改了一下，这时获得了 100+41+20。

我一直没有想去把给我的 T2 的 set 换掉，后面就一直在卡常，但是完全跑不动，于是倒闭了。

出来发现大家带 log 的莫队全都 58 了，难过。

Day 2

感觉上午讲座也太水了，十点五十跑路回酒店，吃必胜客，吃撑了。

睡了一觉去考试，看题，发现 T1 是交互，我左边的哥们一直在嗯嗯啊啊的很烦，打扰了我的思考。想了半个小时发现会 0 分，于是跑路了。看了一眼 T2，感觉不是特别有思路，于是跑路了。然后就看 T3，感受了一下觉得应该是暴力搜索剪枝题，然后我一开始写了一些要用哈希表维护的东西，结果跑出来发现连 5e6 都跑不过去。/qd。然后后面稍微改了一改，5e6 跑了 9s，很倒闭，此时获得 32 分，过去一个半小时，先从 T3 跑路。

看了一眼 T2，有显然的贪心策略，然后贪心完了发现可以递归到一个后缀，想了想代码很好写，先猜了一发上去，结果直接过了 73 分，然后我意识到 T2 应该是简单题，但是最后一个 sub 应该比较麻烦，于是又跑路去看 T1。此时还剩两个多小时。左边的哥们非常吵，我肘击了他一下叫他闭嘴。

认真的思考了很久发现 query(x,y,z) 最大的三个点中有两个点是直径，然后可以问 2n 次确定具体哪两个点是直径，先写了一个 n3 的过了 16 分。然后我又想了 114514 个做法感觉都不大行（其实细想都是可做的，但是我根本没细想），然后发现一个事情就是你考虑这个东西实际上是连续的，也就是你把 x,y,z 中的 x 往相邻的方向移动一步答案加一，减一或者不变。所以你可以通过一点一点的移动来调整到最优解，我不知道怎么证明，反正有一个算法是你每次随机尝试调整一个点，如果 query(x,y,z) 变大了就调整，否则不变，这样一定能调整到最优解。我写了一下发现这个东西居然出奇的牛逼，第一发就过了 36 分。然后我尝试了一些简单的剪枝，以及调整初始的位置，然后我把一开始的 x,y,z 设置成 n-2,n-1,n 就过了 41 分。

然后还剩下 40 分钟，我意识到我这个 T1 已经想歪了，感觉彻底没救了，于是回去给 T3 卡常，把 vector 换成数组，然后卡过去了，得分 41+73+44。

最后半小时没事干了，感觉 T1 太没救了，跑路去看 T2，感受了一下似乎 100 分比较困难，然后我尝试写暴力，最后没能冲过去。

出来了以后发现 T1 并不是特别可做，这下没倒闭，但是因为 D1 挂了 17 分被 114514 人打败了。

后记。

晚上和 @Farmer_D @Fucious_Yin @Microscopic_WaXeR 吃饭，然后发现游戏厅，然后去投篮了，被 Farmer_D 打爆了，太有实力了。然后又发现游戏厅有台球桌，租了一个小时，又被 Farmer_D 打爆了，太有实力了。

开心。

后后记。

第二天晚上和 @Farmer_d @Fucious_Yin @Microscopic_WaXeR @Cry_for_themoon 继续打台球。

被 Farmer_D 带飞了，太有实力了。