(PKU)WC2025 游记

听说洛谷游记不能用 * 来着，那就都改成宋了。

早上高速过来 50min，很快。上午开幕式，不知道讲了啥。

中午和群友吃了个饭，酒店太远，考场门口随便找了个角落休息了一下，然后进考场。

试机懒得写了，写了个 ntt 一个 stress 下播。

开题，t1 一眼不会做啊，分析了一下，好像是要给一张图加边使得最大独立集 $<a$。还是不会做。放了，看 t2，数据结构，好。询问是类似区间数颜色状物，研究一下发现 $lst$ 变化量均摊一下是 $1\log$ 的，然后大概是三位偏序状物，应该是会做了。

再看 t1，根据 noi d1t2 的经验，我们猜测团一定最优，写了个 $O(n^3)$ 本地只要 1.5s，稍微卡个常过了，宋完了。然后开写 t2，写了大概 40min 过了。此时才过去了 1.5h。

还有 2.5h 来大战 t3！看题，$O(n^2)$ 是简单的，先写了一个，对拍能用。然后对着特殊性质 AB 开始自闭。发现要维护 dag 可达性状物，$10^6$ 也没法 bitset。红温的我开始写假的线段树合并，发现根本过不去。

上了个厕所，发现其实不需要保留所有状态。改了一下把第三个包过了，大战 1.5h 终于获得 50 分！

非 DAG 也是容易做的，大概就是缩个点，写了一下赶紧还有些细节，比如要判每个 SCC 点数是否 $>1$，改了半小时才过。75 分。

还有最后半小时，能战胜最后一个包吗？做法是类似的，稍加思考就开写。57 分的时候终于写完了，交上去等了好久评测，结果后三个包全都 TLE！

赶紧开始加一些优化，最后一分钟交了两发，比赛结束了。疯狂刷新提交，第一发还是 TLE，我认为没希望了，关电脑走人了。

出来打开手机一看，我怎么最后一发通过了？？？？绝杀！晚上去吃了兰州拉面。

PKUWC day1: $100+100+100=300$。

酒店早餐感觉还行。上午听说是讲 AI 打 MC，真宋，懒得去了，不如直接在酒店打 MC。

中午很晚才从酒店出发，11：50 才走到食堂，险些没饭吃。吃完饭去了昨天一样的地方休息。

开赛。先看一眼题目配置，交互，最优化，数数。按照以往 PKUXC 经验，每天的 t1 应该都是签到题。于是开交互。

但这也太难了！我想的大致思路是随两个点，然后 $n$ 次询问问出这条链，但是没法确定链的顺序。。想了 1.5h 无果，开始红温，赶紧先去看一眼后面的题，t2 看出一个简单的 dp，写了一下直接把前面四个包都过了，73 分，想着还行，最后一个包应该不比 t1 值，先放了。比赛过半，再看 t3，似乎 24 分很快能写完，遂写之。

继续大战 t1，发现再用两倍链长次询问可以问出链的顺序，然后对于每个非链上的点，再分别用两次次操作可以确定属于链上哪个点的儿子。但是又不会了。眼看时间所剩无几，先把前面这部分写了，后面拼了个 $n^2$ 次操作找 $fa$ 的做法取之 16 分。比赛过去了 3h，只有 $16+73+24=113$，感觉要寄，彻底红温了。

赶紧继续大战 t1，又想了好久终于发现好像可以直接找一个直径的端点，然后对和她属于同一个子树的每个点直接问距离！这样有一个 $4n$ 次的做法，赶紧写，写完调完只剩 20min 了，终于获得了 83 分。

接下来加了一些随机化和常数优化，但是似乎没什么用，$3n$ 的做法也不会，时间就这样走完了。

应该是 OI 生涯最后一场 PKUWC 了，取之 $0$ 题，真是宋完了。出场一问，大家好像都基本过了 t1 或 95 分，然后在 t2 和 t3 大显神通，似乎是垫底了。或许比赛策略上出现了严重问题，亦或是 day2 的运气全用在了 day 1 的绝杀上吧。

晚上回酒店干了一些神秘事情。

PKUWC day2: $83+73+24=180$。

开题，不会 T1，想了一会儿突然发发现 $a_i\in [1,m)$，宋。开写，发现过不了 pretest，以为假了，开始思考一些奇怪的东西。结果发现双指针写挂了，宋。

看 T2，想了好久想出一个模拟费用流的 $3\log$ 做法，开写，写了将近 2h 过小样例，大样例毛都不对。突然意识到自己有一步分析错了，爆。

换一下脑子，先看 T3，胡了一个 $O(n^2)$ dp，一看这不是直接线段树优化一下吗？开写，先写一个 2log，只能 85，改成线段树二分就过了。

没时间了，赶紧开始拼 t2 暴力。然后随便猜了一个贪心开写，写完过了所有 B 性质的答案。没时间了，把暴力接上，结束了。

WC: $100+62+100=262$。

好像是一个金牌线附近的大众分。流汗黄豆。