PKUWC 2025&WC2025 游记

· · 生活·游记

PKUSC 2025

day -2

我居然还没有逛过谷子店，决定 Just Do It ，发现居然没有想买的。

代价是我妈对我的信任度，被她警告了【数据删除】很猖狂，好吧确实是我的错，我还真没和她说过。

day 0

酒店优质早餐。

抓紧时间玩，去鲁迅故居被告知周一 5:00 闭园，倒闭了。

然后吃了个火锅（我不是从 SC 来的吗？），吃完去沈园看绍剧，我只能评价爱情故事都多少带点魔怔

day 1

报道忘了，开营忘了。

午饭一般，毕竟免费。

二十分钟光速试机，丢了个缺省源和对拍板子交了几发就跑了，诶为什么突然出现一道交互？是不是要考？

13:00 开始第一试

开题，感觉 t1 不太好做， t2 有点会做， t3 不太可做。

感觉 t1 难度像是签，做了 45min 里想了一车构造结果只有 a=2 和 a>b+1 的分，这时 14:05 。

有点小慌，决定先开 t2 ， t2 显然不同深度贡献独立，查区间可以莫队。

但是只想到了对每一层建一棵平衡树和树状数组，复杂度高达 \operatorname{O} (m n \sqrt{n} \log n) 我靠倒闭了要。

后来越想越歪，开始尝试把所有点放到一棵平衡树上，拆 lca 深度到两个点上等等，期间想出一个解法但拼不回去，感觉大概率是假的。

期间想到了有个经典做法只支持删除和撤销可以干掉平衡树，但是感觉没什么用，毕竟瓶颈是在树状数组上查答案。

好像这里弄了 25min ，然后又看了一眼 t3 ，好像有点想法了，决定先把 t2 暴力写了，写完 14:30 。

去想 t3 10min 后搞出来个东西，忘了是什么，感觉能做 b_i=i 且 DAG ，反正就是决定先写暴力。

然后暴力死活调不过？？？

vocal 怎么读错题题了？？？改改改，觉得自己又会了 b_i=i 且 DAG

怎么暴力还是不对？？？

感觉不妙， 34 分妥妥倒闭了啊。

小破防，一边提醒自己不要复刻 noip ，一边打 t1 dfs ，因为感觉手跑不出更优的构造了，打完放一边对拍去了。

回去看 t3 ， vocal 怎么还是没读对题？？？改改改，过了，这下不觉得自己会 b_i=i 且 DAG 了

此时 16:00，只剩 1h 了

回去看 dfs ，你怎么连 a=3 ， b=3 都跑不出来？？？这就是无优化 dfs 的魅力吗。

问候了出题人一会决定手动枚举方案，确认了是 a+b 个点里选a个满图再选最小的两个在连成满图。

手枚出一组方案发现之前的做法假完了，然后我写了个

枚举最小两个满图大小，算连边数量？？？

中间还背错了一次结论（那么 的结论自己推不行吗非要背，该挂），幸好改改过了，这时 16:25 。

然后交替想了一下 t2 ， t3 ，毫无收获。

最后 100+24+20=144 ，好高的运气成分，但感觉这个分数差不多是人均。

考完问了一圈，为什么一车人 t1 10 分？为什么一车人 t2 43 ， 77 甚至 100 ？？？

咬尾 lnh 以获得 t2 做法，然后被告知算答案的信息只用一棵树状数组，这样就有 43 了，好好好人均来到了 161 。

这我不会？？？这我不会？？？这我不会？？？这我不会？？？这我不会？？？

退役把哥们。退役把哥们。退役把哥们。退役把哥们。退役把哥们。退役把哥们。退役把哥们。

然后被告知用数组代替平衡树可以拿到77分，因为如果区间长度期望为 \operatorname{O} (\frac{n}{w}) 则数组查前后继时间复杂度为 \operatorname{O} ({w}) 虽然边界情况一点小不对但常数低就是能为所欲为，好好好人均来到了 197 。

最后正解就是运用经典做法并使用只删不加回滚莫队 + 用分块代替树状数组做到 \operatorname{O} (n\sqrt{u})

day1 人均来到了 220 ！让我们恭喜它！！！（不是

然后认为我 t1 能爆标，基于前面做法可以做到 \operatorname{O} (T n\log n) ，被告知 dp 均摊后都比这个低。

被 qye 提醒鸽笼原理，啪，很快啊！会了 \operatorname{O} (T) 并发现 a+b 个点里选 a 个满图再选最小的两个在连成满图的最小边数 不就是 a+b 个点里选 a-1 个满图的最小边数 吗？？？当然这两者等价，我试飞舞啊这题该 \operatorname{O} (1) 分钟做出来啊。

依然不会 t3 \ge 20 的做法。

晚上做出了 day2 正常发挥能有优异的预测。

晚上再次发表 day2 有交互的观点，被问我没做过交互怎么办，我把告知只要会编译和测样例就行，甚至只要不是 t1 拿个极低分甚至 0 分都没关系。

我给别人讲这个干嘛，我自己碰上有交互场基本上都被创飞了，有这能力？？？有这能力？？？有这能力？？？有这能力？？？

想起来为什么忘了开营，我根本没去，哈哈。

day 2

上午的讲座怎么不在 THUWC2024 前讲啊（恼），现在完全懂了。

午餐怎么比昨天更不能吃了。

午休懒得回酒店了，在阶梯教室休息，左边有两个卷怪（ qye 和 cbh ）

13:00 开始第二试

t1 是交互？交互是 t1 ？？？啥情况。 t2 读错题了（一共删 k 个 -> 每个点删 k 个），于是认为 100% 网络流， t3 一如既往只会暴力。

先做 t1 ，花了 20min 想到可以先选一条链，求出每个点到链距离，把每个点挂到链上然后分治，查 \operatorname{O} (n^2) 次操作 1 ，但感觉有一车细节，不好写（我不造啊我现在咋觉得这东西很好写）,觉得 t2 是流的话 70% 是个签。

然后去看了 40min t2（啊？），画了一堆图找不到对的啊？？？又往上套了一堆东西，还是不对，现在 14：15 ，还没动过键盘。

这怎么行啊？？花了 30min 把 t3 sub1,2,4 过了，发现 sub3 是卡常，试图得分未遂（为什么，当时， dp 调了两年？？？）。

回去看 t1 ，发现一开始的做法还要求出当前链上点的顺序才能算答案，这我不会啊，想了半天只会查 \operatorname{O} (n^2) 次操作1求顺序，这拿个毛线分啊（现在分析了一下是总共 \operatorname{O} (n^2) 次，晕）。觉得一对相邻点的性质比随的一条链要好，但不知道好在哪里，抛开了分治想了一下二次搜索，没甚成果，还发现了一个 corner case 做不来，服了。

这下好了，滚回去做 t2 ，还是不会怎么流啊？？？这就很扯淡，怀疑自己题读错了。 vocal 还真是！！！遂发现这题至少是个 dp ，写了个贪心过了样例，交上去 WA0 ，想了想发现策略确实不简单，开始写 \operatorname{O} (n^2) dp ，写了过了样例，交上去还是 WA0 。感到迷惑，有点急了，感觉是一开始不能模 k 导致的，一气之下把 dp 改成 \operatorname{O} (n^2 \times \frac{\sum a}{k}) 交上去拿了 73 ？？？它甚至不愿意造一点 k 比较小的数据？反正是 IOI 赛制，分拿了就不管了，现在 16:30 。

最后 30min 感觉脑子完全不清醒，去写了 t1 查 \operatorname{O} (n^3) 次操作 1 ，这有分吗？写得差不多了还发现假了，然后就摆了，回去卡了卡 t3 sub3 ，还是没分，依然不知道为什么要么用不上操作 2 要么用超，死不瞑目啊哥们。

最后 0+73+36=109 ，还是好高的运气成分，但感觉这个分数要远低于人均。

问了一圈，好好好， t1 平均五六十，还有快九十分的，似了啊，这还个拿个毛线优异，而且为什么一车人都拿到了 t3 的卡常分。

被告知 t1 就是二次深搜，不然操作 2 怎么用？还被告知了最远点一定可以是直径的端点，分类讨论一下就能证明。玩蛋啦。

昨天晚上问我的那个人保龄了，原因竟是死磕了 t1 。害怕。

t2 说是模 2*k 就可以了，感觉很平凡，要不是过了也应该能想到。

一共 100+24+20+0+73+36=253 ，只希望别给我个良好就行。

WC 2025

后面再补。

后记

太好啦是“【中文】与【英文、数字或公式】之间应以半角空格隔开。” 我们有救啦。