PKUWC 游记

· · 生活·游记

PKUWC2025

## Day 1 来到了~~奶~~龙山书院，看之前的宣传等方面，总觉得这个学校看起来非常贵族啊！感觉比 SXYZ 牛很多的样子！ 进门后发现学校的构造有点奇怪啊，怎么看起来这么绕的！而且主要道路都在楼上走，感觉没啥大马路，很怪呢！与 SXYZ 完全不一样啊。 报道，发现报道的老师都是学校里的信技老师，差点没绷住。 下去拍照，结果 MK 记错时间一直没到，最后极限赶到拍集体照。 去报告厅听讲座，好像网络比 APIO2024 牛很多，基本不卡，于是尝试看群 u 面积，但是自己直面到了一些比较熟的群 u，一些比较知名的选手都没有去认识/qd。 第一次线下见到了 @lzyqwq 和 @lycc。 吃饭，因为前面上了个洗手间浪费了很多时间，而且排队随机出现米饭不够等情况，最后 11:30 才吃上饭，这时候别人都吃完了 /qd。 下午进场，门口出现了一些比较幽默的情况。 试机题是去年 D2T1 和元旦激光炮/xia，不会今年有交互题吧/xia，不会元旦激光炮/ng，也没有尝试打板子，因为之前似乎每次打板子都没有用上/fad。 13:00，哦不 21:00 准时启动，先看 T1，我会 $a>b+1$！先交一个，获得了 $5$ 分，我还会 $a=2$，于是获得了 $10$ 分！ 我擦，然后怎么做，一点都不会。 用直觉写了一个 DP，然后交上去喜提 $10$ 分/ng。 看起来好阴间了，我还是去看 T2 吧。 看了下 T2，我去，数据结构。 看了下 T3，太长了，先不管。 读了一下 T2，发现因为只有深度相同的点会撞一起，于是可以对深度相同的点建虚树，这个树的树高是 $O(\sqrt{n})$ 的，所以只需要暴力扫描线就可以做到 $O(n\sqrt{n}\log n+m\log n)$，感觉看起来挺有道理的样子！ 但是仔细想了一会发现这个做法又难写空间又大常数又大，很怄火，码了一部分先咕咕咕了，回去大战 T1。 发现 T1 写的 DP 连 sub1 都过不去，但是先发现询问一个菊花删掉一个点的次数可以减少，然后再交，发现没变化。 尝试把 sub1 手模出来，发现 $a>b$ 的时候应该都没问题，$a=b$ 的时候我的输出是 $a+4$，感觉比较优秀，但是发现 $b$ 大的时候数量级还是比较爆，太不牛了。 在草稿纸上无限手玩，拼尽全力无法战胜，找也找不到一个最优的 $a=3,b=3$，玩了好久发现我居然能询问一个三元环来排出两个坏的和一个好的，交上去过了 $a,b\leq4$，然后发现我居然还可以询问一个大小为 $n$ 的团来排出一个好的 $n-1$ 个坏的，于是把这个拼上去，搞出一个 $a^3$ 的 DP，交一下发现直接过了 /xia，这个时候已经过了 1.8h 了，感觉被这个 T1 击杀了。 读完了 T3 题意，根据题意写个暴力，写完才发现怎么每个点可以出发到它的传递闭包/xia，改了一下获得了高达 10 分。 开始大战 T2，想想除了这个 $O(\sqrt{n})$ 的虚树高以外还有没有别的做法，手玩了一下暴力，发现只关心祖先的分布就可以在这个虚树上启发式合并，然后就变成了 $O(n\log n)$ 个修改 $O(m)$ 次查询的带修区间数颜色，直接启动一个 cdq 分治不是对完了？ 然后开始写，写到一半发现虚树不会建啊，凭一些记忆手搓了一个奇奇怪怪的虚树建法，然后开始写下去。 写完还有大概 1h 左右，然后开始调。 结果第一个调出来的地方就是虚树建错了，我憋憋，改了一下发现还是不对？我去，怎么要把跳出去的祖先给删掉，这个加上就过样例了！ 交一发，怎么 WA 光光了！！！！ 好像没啥好的调法，尝试写个暴力开始拍，拍了一会发现怎么死透透了？ 调了一会发现我怎么虚树又建错了/hsh，冷静一下，重新又改了一个看起来比较对的虚树方法，对着 $n=8,q=8$ 拍一下好像没啥问题。 这时候只剩大概 10min 左右了，只能交交交，一看，又全 WA/ng/ng/ng。 把拍子开到 $n=80$ 发现一发拍出来了，不是我不会虚树又建错了吧？？？ 没救了，遗憾立场。 出来发现大家都比我高，cyf AK 了，太恐怖了。 问了一下大家 T1 几分钟过的，除了少数过的很快外其他都基本 1.5~2h 才过的，太吓人了。 没到大众分，要没有优异了！！！！！！！！ ## Day 2 讲座，居然是两个人讲不同的内容，第一个人讲的是训 AI 用于 Game，第二个人讲的是人形机器人，感觉内容还挺互补，也挺有趣的！ 中午学聪明了，加速奔向食堂，这次直接就排到饭了啊！ 吃完饭直接去转了一下寝室，发现寝室里还是有插座的！但是被床挡住了，比较幽默，居然是一间浴室+一个厕所的配置，比较牛！就是感觉刚装修好味有点大之外其他都吊打 SXYZ 现在的寝室了。 下午直接进场，没有找到昨天丢失的黑色帽子/ng。 开题，T1 果然是交互！T2 T3 题面都好短啊，发现 T2 是一个奇奇怪怪操作的最优化题，甚至不能线性规划，而且没有指数级暴力部分分，不会是什么阴间推性质不可做题吧？ T1 在草稿纸上疯狂手玩，发现如果我知道了一个长度为三的链的话我就可以知道非常多的信息，如果我把这个链搞出来可能就可以做了吗，结果手玩了好久，没啥进展。 看 T3，发现暴力很好写，直接拿下前两个包，第三个包换上狄利克雷前缀和也过了，看起来这个第四个包应该硬做做也能过 T1 完全不想推，非常怄火，还是看 T2 吧，想了一个看起来很对的贪心策略，那第一个包直接写一个记忆化搜索就过了。 毛看看这个记搜的状态就非常少，于是用哈希表吓改改，发现过了一火车点，再改改直接把 $c=1$ 也过了，直接拿到了 $73$，我问号。不会分析复杂度，看 $c=1$ 都过了猜猜它跑的很快，于是又交了几发，没啥进展，算了不管了/hsh。 还是来看看远方的 T1 吧，总不能一分都没有吧，感觉刚刚那个想法有点阴间。 尝试从一些暴力入手，瞎编了一个平方级别的，发现一分都没有，感觉没啥前途，真是怄火了。 回到之前的想法，发现可以三个点的链有点难搞，但是我可以搞出一组相邻点，这个足够求出直径一个端点，然后再瞎搞搞把直径另一端也求出来。 写写写，细节还有一点，但是写着还是挺顺的，很快过了样例，交上去全 WA。 本地稍微拍了一下，拍过以后直接交，怎么除了第一个包都没过？ 不是我问号了，这哪里有问题啊，把 $n$ 开到多少都拍不出问题啊，幽默吧，这几把的咋搞啊。 随机造几组 hack 也都没问题啊，问号了，再交发现还是只过了第一个包。 结果数样例的时候不小心吧 $t=1$ 输成了 $n=1$，然后一看直接 WA 了，定睛一看数据范围，怎们是 $1\leq n\leq 10^5$ 啊！！！！！！我一直当成 $3\leq n\leq 10^5$ 做的！！！！！想着总不会有出题人这么无聊吧！！！！！ 把 $n=1,n=2$ 拼上获得了 $56$，无语，感觉这个东西真的玩原神玩的！！！！！ 分析一下发现我极限情况可以卡到 $6n$，其中有 $2n$ 应该可以随机化掉，这 $2n$ 里面也有概率一个 $n$ 不会跑进去。 于是交了个随机化，还是 $56$/ng。 感觉我这个东西还是太暴力了，应该没救了。 $56+73+32=161

出场一问发现大家要么比我高，要么都爆的有点惨，感觉这个区分度太奇妙了。

upd： 场上最后的建虚树是对的，不知道哪里挂了，赛后复现一下直接是对的/qd，以及那个根号树高应该没啥用，严格比启发式合并菜。以及游记变成单 PKUWC 游记