PKUWC 2025 游记

· · 生活·游记

Day0

坐飞机到酒店。

Day1

上午是开幕式，很无聊，下午的试机和正式赛连在一起了。

试机的时间是 12:20~12:50。

试机有两道题，第一题是去年最简单的一题，第二题就直接搬了 UOJ #52（交互题）。

先把第一题过了（去年做过），想了一会第二题，没什么想法，于是交了一发 sample code 并拿到 WA 0 的好成绩，试机就结束了。

我想着试机都有交互题那正式赛也应该有交互题。

正式赛的时间是 13:00~17:00。

三道题分别是电池检测、Ancestors 和基础博弈练习题，没有交互题。

仔细观察了一下 T1，感觉有可能可以给电池分组，每组内的电池都两两尝试，这样只要分出 a-1 组就能保证在最后一次尝试的时候试出来，感受一下，尽可能平均分应该就是最优的，写了一下就过了。

然后就在 T2 和 T3 之间反复切换，最后过了很久也不会比 24+20 更多的分数，最后没办法，只能写 24+20 的暴力分了，最后空出来了将近两个小时的时间。\color{white}\text{全部用来玩 Emacs 了。}

最后得到了 100+24+20=144 分，成功拿下大众分。

到场外，发现比我低一年级的和比我高一年级的统统考得比我高一大截，感觉寄了。

Day2

比赛时间依然是 13:00~17:00，上午听了一下讲座，意外地不感觉无聊。

由于试机有交互题，所以我猜测第二天肯定会有交互题。

第二天的三道题分别是网友小 Z 的树（交互题）、盒子和数字变换，被我猜中了。

首先观察 T1，感觉要求是要找到一个不超过 3n 次询问一的做法，但是到最后也没找到。发挥人类智慧找到了 O(n) 次询问一的做法，后面精细实现了一下应该刚好是 4n 步，于是获得了 n\le7\times10^4 的 83 分。

然后观察 T2，有一个显然是假的贪心做法，但是当 c=1 时显然是对的，用一个线段树优化一下就拿到了 11 分。然后感觉把这个做法改一下变成贪心加 DP 就可以做到平方 \log 级的复杂度，交上去得到了 49 分，\sum n\le5\times10^3 的 24 分没冲过去，于是又想了一个优化，可以把线段树去掉，复杂度变成平方级，得到了 73 分。

最后还有不到一个小时打 T3，想着要把 r\le5\times10^6,B\le40 的 32 分拿到，于是写了 O(Br\log r) 的暴力 DP，得到了 24 分，卡了卡常，还是 24 分，最后想起了狄利克雷前缀和，成功将复杂度优化到了 O(Br\log\log r)，平稳地拿到了 32 分，最后只剩了 5 分钟左右。感觉如果时间再多一点，有可能还可以拿到 l=r,B\le4 的 12 分，不过也不一定。

最后得到了 83+73+32=188 分，成功拿下小众分（？）。

总分就是 144+188=332 分了，也不知道高不高。

问了一下第一天考得比我高的同学，好像有很多第二天考得都比我低。

似乎翻盘了？

Day3

由于我太菜了没有 WC 可以参加，于是直接坐飞机回家了。

最后的总结就是要加强数据结构吧，如果 D1T2 能拿到超过 24 分的话应该就没有那么慌张了。