PKUWC2025 游记

· · 生活·游记

书接上回：CTT2024 游记。

省流：275 + 217 = 492，1=。

Day 1

开场看了 T1，想了 1 分钟后大概有思路了，11 分钟整的时候通过了这题，感觉这题没啥区分度。

看了 T2，会了莫队算法，想了 20 分钟突然意识到莫队能过，写了一下在 70min 的时候发现最后两个包过不去。

把求 LCA 改成了 \mathcal{O}(1) 写法就只 T 最后一个了，很好。

这个 RMQ 常数看着就很大，所以在链表的边上存储 LCA 的深度，就过了，这个时候 100min 左右，这优势不在我？

想了一会 T3 发现怎么时间过半了，很慌！

T3 完全不会，开始随便写个暴力，大概就是记 f_i 表示 i 的必胜开始位置集合……

这个时候走过了一个很帅的志愿者查身份证，然后核验我身份的时候看的很快（？

一种似曾相识的感觉…上次这样…是 PKUWC2024…？xht…？

然后对着我的电脑一番操作检验身份（？

点开分数看到 100 + 100 + 0 后摸了摸我的头（？

（这分明不是在检验身份啊喂！）

好像还挺舒服的 qwq

这个时候我们大胆猜测 f_i 只用对于奇偶分别保留一个极长合法前缀和一个极长合法后缀即可！

调了调过了 Sub 3。

再加了个 Tarjan 过了 Sub 1？？？

再调了调过了 Sub 4。

再微调了一下过了 Sub 2。

还有 45min，一个 Sub 5，优势在我啊！

（小插曲：断点调试的过程中先备份了一下代码再调的，最后发现更改后的代码和正在调试的代码不是同一份，浪费了 5min/dk）

然后就开始各种乱搞，包括但不限于在奇怪的地方假如二分，但最后还是无果，随着最后一分钟第 31 次提交的 WA 跳跃在屏幕上方，我知道，我这场比赛也就这样了。

我开摆了。我也不想有一个比赛结束前测不出的第 32 发提交吊着我胃口吧！

最终得分：100+100+75=275。

出来一看大家怎么都这么高！好多个 275，好像群里还有一车 AK，好可怕呀！

但应该还是稳稳上线了，只要明天不翻车就行！

Day 2

开场 6 分钟会了 T1，然后假了。

过了几分钟意识到求的是答案可能是三条路径中的任意一条，想了几十分钟不知道怎么修，大概有一个 5n 次操作的做法。

突然意识到 70min 了，还是 0 分！看完 B 会了 \mathcal{O}(n^2)，感觉人人都能过？

然后花了 20min 写 + 调，再花了 10min 把 A 搞到 70 分。

怎么没有志愿者来摸头

给 C 写了个最纯暴力，2h 的时候拿到了 150 分，一题没过，很慌啊！

然后给 C 卡了个常，搞到了 44 分，尝试过 B 无果，又对 A 尝试了一堆乱搞失败。

然后把 A 的求 dis 改成随机若干个点询问取 min 就 95了？？？

这个时候还剩 30min，在 B 和 C 之间反复横跳，B 猜了个假结论但是把 c=1 过了？

拼一下 B 拿了 73 分，最后 10 分钟，我赌 A n=10^5 的时候可以随机 1000 个点不可能成为答案！然后加上就过了？？？赢！

最终得分：100+73+44=217。

好像最高 \boldsymbol{554}，被吊打了，不乐，还是太菜了/dk

Day 3

下午加训非对称随机博弈论，打了一把金雀（

晚上去吃了火锅，见了网友（

大家吃菌子一定要煮熟啊！

书接下回：WC2025 游记。