PKUWC 2025 游记

· · 个人记录

Day 0

来到绍兴，感觉酒店比较不错，但是只有一个椅子，于是我发挥传统艺能，把行李箱立起来，坐行李箱上，晚上大概 11:00 睡觉。

Day1

早上教练说 7:40 起来，于是我闹钟订的 7:40，但是我起来一看，6:40，原来是窗帘没有关严，然后天亮的很早，然后又躺了一下就起来了。

吃完饭就去报道，感觉速度比 T 快很多啊，根本不需要排队，然后是开幕式，完了之后就去吃午饭了，感觉这一天的午饭比较抽象，不是很合我胃口，也没怎么吃饱。

先试机，进去一看，元旦激光炮？？？？？

然后就意识到了一定会有一个交互，想起了我 CTT 的时候三个交互一个不会，感觉有点倒闭。

然后还是把两个题都写了，在桌子上趴了一下。

于是正开，想着这个 T1 无论如何不会很难吧，于是想了一下，感觉不是很会，看特殊性质，发现会 $a>b+1$ 和 $a=2$，写了发现过了这两个包。然后想 $a=3$，猜了一下感觉和 $a=2$ 差不多，分成两个部分这样两边都问完全图就对。 这不是我们百万富翁吗？写了平均分直接过了，所以为什么 $a,b$ 是 $10^3$ 啊？ 然后看 T2，想去重，然后感觉把每一层都拉出来建虚树暴力合并复杂度不会超过 $O(n\sqrt n)$，唐了一下没有想到本质不同的合并只有 $O(n\log n)$，然后就变成了 $O(n\sqrt n)$ 次单点修改，然后 $m$ 次查询，写了个分块树状数组，居然直接过了？ 目前用了 75min，感觉还不错。 换到 T3 先花了 30min 写了一个暴力，大概搞懂了这个题在干什么，然后一直对着 AB 性质自闭，没有想到并不需要求每个点是不是必败点。 然后很红温，一直不会做，就开始乱搞，先写了个复杂度显然炸的线段树合并，果然被卡了，然后最后 30min 写了个，只记录一个点能到达的前 $20$ 小的必败点，然后交上去过了，很震惊，不太理解，当然后面知道了其实只需要保留最小的就可以了，非常优美。 然后最后把 sub4 写了一下，极限调出，于是就以非常搞笑的方式获得了 $100+100+75$。 然后又想了一下 sub5，感觉知道了这个还是不会做啊？？？ # Day 2 不知道是不是有点冷，早上起来发现右边耳朵后面一直在一跳一跳的痛，然后一直持续了一天，然后考场上每隔一小段时间就会痛一下吸一口气，感觉给左边老哥带来了不太好的比赛体验 /kel/kel。 早上的讲座很有意思。 今天中午有时间休息了，但是头痛并没有好转。 下午去了考场，一看 T1 是交互，感觉有点倒闭，先硬想，发现可以用常规的方法找直径，但是操作次数是 $5n$ 的，写了一下得了 $70$ 分，然后对着这个卡常，减掉了一个 $n$，有 $83$ 分，感觉不太好进一步优化，就摆了，去看后面的题。 拿到 T2 想了 5min 得到了一个 $O(n^2)$ 的 dp，然后大概想了一下不会优化，就直接写了，发现 $O(n^2)$ 有很多分，然后加上了一个 $c=1$，就有 $73$ 分了，于是扔掉去看 T3。 T3 一上来先写了暴力，能过 $10^6$，但是 $5\times 10^6$ 跑不了，然后就对着这个东西卡常，卡进去了，又写了一个 $l=r$ 的，观察到了其实 $B=100$ 的时候状态数并不多，但是不会找，于是没有下一步了。 这个时候大概还有 $1h$，然后就继续对着 T1 卡常，发现什么用都没有，还是 $83$。 于是总分就是 $100+100+75+83+73+44$，好像 T1 最后是增量，而不是直接找直径。