PKUWC 2025

· · 生活·游记

坐了 6h 高铁到了绍兴，在高铁上用掉了 13G 流量。

Day1

进场，发现没带笔。

蚌埠住了，不管了，尝试使用画图软件，但是并不知道 linux 有什么画图软件。

随便找了一个，发现不好用。

试机题看了一下，发现不会做。

于是不管了，写了个拍子，写了个 NTT 板子。

快进到比赛开始。

一眼注意到 T3 题目名称：《基础博弈练习题》。

开始看 T1，读完题发现非常神秘。

瞎蒙了几个东西只能过性质。

想半天，从图论考虑，转化成图论模型。

不知道为啥，猜测了一下答案中的每个连通块一定是完全图，写了个暴力发现居然是对的。

给暴力卡了卡常最后 O(n^3) 过了 1000。

看 T2，感觉是个 ds。

想了一会感觉不太会 polylog，开始考虑莫队。

很快会了莫队做法，复杂度 O(n\sqrt m)，这个题 n\le 10^5,m\le 10^6，时限 4s，算下来刚好能跑。

写完之后交上去，居然连 m\le 4\times 10^5 都没过。

卡了一会常过了 77pts，本地满数据跑了 3.5s，但是评测机比本地慢，一直 TLE。

1h 后决定放弃 T2，看 T3。

首先胡了个 n^2 获得 20pts。

发现第三档居然有整整 30pts。

观察到一个性质，写了第三档，过了 50pts。

第四档比第三档少了个 DAG 性质，于是加个 tarjan 过了 75pts。

此时还剩 1h，于是在卡 T2 常和想 T3 正解反复横跳，最后没有多得分。

Day1 总分：100+77+75=252。

Day2

这次带笔了。

开 T1，居然放交互，真没素质。

想半小时瞎胡了一个，交上去 WA 了。

拍了一会，改了改做法过了 O(6n)。

加了个优化过了 O(5n)，此时 70pts。

想了一会不会进一步优化了，于是开 T2。

T2 看着像是个直接贪的题，但我显然不会。

于是写了个 n^2 暴力，结果 WA 了，连性质都没过。

写了个性质，和暴力拍，调过了暴力，获得 73pts。

开 T3，直接 dfs，过了第一档和第四档。

写了个 dp 过了前两档。

加了个狄利克雷前缀和过了第三档。

此时 T3 44pts。

下一档是 r\le 10^8，而最后一档是 r\le 4\times 10^9。

感觉获得更多分需要比较接近正解，于是接着想 T1。

T1 想到了个优化，加上之后过了 95pts。

感觉这个程度可以了，于是准备去想 T2，临走之前瞎加了个东西，交了一发：

怎么过了？？？？？？？

后面还剩 2h，罚坐 2h 想 T2 想不出来，遗憾离场。

Day2：100+73+44=217。

两天总共 100+77+75+100+73+44=469，但不知道大众分多少。似乎比大众分高一点？